E2. Обновление котов (сложная версия)
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственным различием между простой и сложной версиями задачи является наличие запросов удаления: они присутствуют лишь в сложной версии.

Компания «Interplanetary Software, Inc.» вместе с компанией «Robots of Cydonia, Ltd.» разработала и выпустила роботов-котов. Эти электронные питомцы умеют мяукать, ловить мышей и всячески развлекать хозяина.

Недавно разработчики из «Interplanetary Software, Inc.» решили выпустить обновление программного обеспечения для этих роботов. После обновления коты должны уметь решать задачи, связанные со скобочными последовательностями. Одна из таких задач приведена ниже.

Сначала немного погрузимся в теорию скобочных последовательностей. Будем рассматривать строки, состоящие из символов «(», «)» и «.». Назовем строку правильной скобочной последовательностью (ПСП), если из нее можно получить пустую строку путем операций удаления одиночных символов «.» либо подряд идущих символов «()». Например, строка «(()(.))» является ПСП, т. к. с ней можно проделать следующую цепочку удалений:

«(()(.))» $$$\rightarrow$$$ «(()())» $$$\rightarrow$$$ «(())» $$$\rightarrow$$$ «()» $$$\rightarrow$$$ «».

Мы получили пустую строку, а это значит, что исходная строка является ПСП. В то же время, строка «)(» не является ПСП, поскольку к ней нельзя применить описанные выше операции удаления.

Будем называть ПСП простой, если эта ПСП непуста, не начинается на «.» и не заканчивается на «.».

Также будем считать, что подстрока строки $$$s$$$ — это ее последовательный подотрезок. В частности, $$$s[l\dots r] = s_ls_{l+1}\dots s_r$$$, где $$$s_i$$$ — $$$i$$$-й символ строки $$$s$$$.

Теперь перейдем к формулировке задачи. Вам дана строка $$$s$$$, изначально состоящая из символов «(» и «)». Необходимо отвечать на следующие запросы:

  1. Даны индексы $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$). Гарантируется, что $$$l$$$-й символ строки равен «(», $$$r$$$-й символ строки равен «)», а символы между ними равны «.». Тогда требуется сделать $$$l$$$-й и $$$r$$$-й символ равными «.».
  2. Даны индексы $$$l$$$ и $$$r$$$ ($$$1 \le l < r \le n$$$), причем гарантируется, что подстрока $$$s[l\dots r]$$$ — простая ПСП. Требуется найти количество подстрок в $$$s[l\dots r]$$$, которые являются простыми ПСП. Иными словами, необходимо найти количество пар индексов $$$i$$$, $$$j$$$ таких, что $$$l \le i < j \le r$$$ и $$$s[i\dots j]$$$ является простой ПСП.

Вы работаете в «Interplanetary Software, Inc.» и Вам поручили непростое задание: научить котов после обновления решать описанную выше задачу.

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

В первой строке входных данных находится два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 3\cdot10^5$$$, $$$1 \le q \le 3\cdot10^5$$$) — длина строки и количество запросов.

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

В каждой из следующих $$$q$$$ строк находится по три числа $$$t$$$, $$$l$$$ и $$$r$$$ ($$$t \in \{1, 2\}$$$, $$$1 \le l < r \le n$$$) — запросы, которые требуется обработать. Гарантируется, что все запросы корректны и удовлетворяют условию задачи.

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

Для каждого запроса второго типа выведите по одному целому числу в отдельной строке — количество подстрок, которые являются простыми ПСП. Ответы требуется выводить в том же, порядке, в котором приведены сами запросы.

Пример
Входные данные
9 8
)(()())()
2 3 6
2 2 7
1 3 4
2 2 7
2 2 9
1 5 6
1 2 7
2 8 9
Выходные данные
3
4
2
4
1
Примечание

Рассмотрим пример из условия.

Ответ на первый запрос равен $$$3$$$, поскольку существует всего три требуемых подстроки: $$$s[3\dots6]$$$, $$$s[3\dots4]$$$ и $$$s[5\dots6]$$$.

Ответ на второй запрос равен $$$4$$$. Подходящие подстроки — $$$s[3\dots6]$$$, $$$s[3\dots4]$$$, $$$s[5\dots6]$$$ и $$$s[2\dots7]$$$.

После третьего запроса строка станет равной «)(..())()».

Ответ на четвертый запрос равен $$$2$$$. Подходящие подстроки — $$$s[5\dots6]$$$ и $$$s[2\dots7]$$$. Обратите внимание, что $$$s[3\dots6]$$$ больше не является простой ПСП, т. к. начинается с «.».

Ответ на пятый запрос равен $$$4$$$. Подходящие подстроки — $$$s[5\dots6]$$$, $$$s[2\dots7]$$$, $$$s[8\dots9]$$$ и $$$s[2\dots9]$$$.

После шестого запроса строка станет равной «)(....)()».

После седьмого запроса строка станет равной «)......()».

Ответ на восьмой запрос равен $$$1$$$. Подходящая подстрока — $$$s[8\dots9]$$$.