406418: GYM102399 B Личность широких взглядов

B. Личность широких взглядовограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Вася — опытный составитель задач для олимпиад по программированию. На его счету множество разнообразнейших задач, с некоторыми из которых вы можете быть знакомы. Как и все великие творцы, Вася столкнулся с творческим кризисом.

Задачу-то Вася придумал, но не может никак придумать остроумную и уместную легенду к этой задаче. Уже который день Вася не выходит из комнаты, он падает в пучину отчаяния, ужаса, одиночества и безнадёжности. Чтобы как-то его развеселить, друг Петя подарил ему строку $$$s$$$, состоящую только из открывающих и закрывающих скобок.

«Ну вот, — подумал Вася, — опять главному герою подарили что-то, чего в реальной жизни никто не дарит. Сейчас, видимо, ещё какое-нибудь свойство припишут этой строке, которое нужно будет вычислить.»

Красотой строки из скобок называется количество её циклических сдвигов, которые являются правильной скобочной последовательностью.

«Вау, как оригинально, — скептически пробурчал себе под нос Вася, — ни разу не видел, чтобы в задачах по программированию требовалось вычислять красоту целого объекта. Ну всё, сейчас мне зачем-то будет надо будет вычислять эту величину на подотрезках и обрабатывать какие-то запросы изменения строки.»

И в самом деле. Для запросов вида $$$(l, r)$$$ требовалось определить красоту подотрезка строки $$$s$$$ с $$$l$$$ по $$$r$$$ (включительно). Помимо этого, поступали запросы изменения определённых символов строки $$$s$$$.

«Замечательно, — разочарованно вздохнул Вася, — очередная скучная задача на структуры данных, не хочу её решать. О, а ведь можно дать эту задачу на какую-нибудь олимпиаду!»

Так Вася и поступил. Докажите Васе, что задача совсем не скучная и решите её.

Входные данные

В первой строке задано целое число $$$n$$$ ($$$1 \leq n \leq 300\,000$$$) — длина строки $$$s$$$, которую подарили Васе.

Во второй строке задана строка $$$s$$$ длины $$$n$$$, состоящая только из символов «(» и «)».

В третьей строке задано целое число $$$q$$$ ($$$1 \leq q \leq 300\,000$$$) — количество запросов определения красоты подстроки.

В следующих $$$q$$$ строках заданы описания запросов. Запросы бывают двух видов:

• 1 x ($$$1 \leq x \leq n$$$). Требуется изменить символ строки $$$s$$$ на позиции $$$x$$$ на противоположный (то есть ( на ), а ) на ().
• 2 l r ($$$1 \leq l \leq r \leq n$$$). Требуется определить красоту подотрезка строки $$$s$$$ с символа $$$l$$$ по символ $$$r$$$ (включительно).

Выходные данные

Для запросов второго типа выведите ответы на них в том порядке, в котором они заданы во входном файле.

ПримерВходные данные

10
)(()()())(
6
2 1 10
2 3 6
1 4
2 2 7
1 5
2 3 6

Выходные данные

2
2
0
1

Примечание

Напомним, что правильной скобочной последовательностью называется скобочная последовательность, которую можно преобразовать в корректное арифметическое выражение путем вставок между ее символами символов «1» и «+». Например, скобочные последовательности «()()», «(())» — правильные (полученные выражения: «(1)+(1)», «((1+1)+1)»), а «)(» и «(» — нет.

Циклическим сдвигом строки $$$s$$$ длины $$$n$$$ на $$$k$$$ ($$$0 \leq k < n$$$) называется строка, являющая собой конкатенацию (сложение) последних $$$k$$$ символов строки (суффикса длины $$$k$$$) $$$s$$$ и первых $$$n - k$$$ символов строки (префикса длины $$$n - k$$$). Два циклических сдвига на $$$i$$$ и $$$j$$$ называются различными, если $$$i \ne j$$$.

В первом запросе рассматривается строка )(()()())(. У неё есть два циклических сдвига, которые являются правильными скобочными последовательностями: сдвиг на $$$1$$$ и сдвиг на $$$9$$$.

Во втором запросе рассматривается строка ()(). У неё также есть два циклических сдвига, которые являются правильными скобочными последовательностями: сдвиг на $$$0$$$ и сдвиг на $$$2$$$.

После третьего запроса строка $$$s$$$ становится равной )(((()())(.

В четвёртом запросе рассматривается строка (((()(. Ни один из её циклических сдвигов не является правильной скобочной последовательностью.

После пятого запроса строка $$$s$$$ становится равной )((())())(.

В шестом запросе рассматривается строка (()). У неё есть только один циклический сдвиг на $$$0$$$.