Правильная скобочная последовательность - это последовательность скобок (символов ( и )), в которой каждой открывающей скобке найдётся закрывающая. Представьте, например, что мы записали какое-то большое матетематическое выражение, а затем оставили от него только скобки - получится правильная скобочная последовательность.

Более формальное определение:

• Пустая строка есть правильная скобочная последовательность;
• Пусть $S$ — правильная скобочная последовательность, тогда $(S)$ есть правильная скобочная последовательность;
• Пусть $S1, S2$ — правильные скобочные последовательности, тогда $S1S2$ есть правильная скобочная последовательность.

Вам задана скобочная последовательность длины $n$ (не обязательно правильная), и $q$ запросов вида $[l; r]$. Для каждого запроса найдите число таких подотрезков $[a; b]$, что $l \le a < b \le r$, а скобочки с $a$-ой по $b$-ую образуют правильную скобочную последовательность.

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

В первой строке записаны числа $n$ и $q$ – длина скобочной последовательности и количество запросов ($1 \le n, q \le 2 \cdot 10^5$).

В следующей строке записано $n$ символов ( и ) – скобочная последовательность, в которой следует искать подотрезки.

В следующей строке записано число $q$ – количество запросов. Дальнешие $q$ строк содержат по два числа $l_i$ и $r_i$ – ограничения для $i$-того запроса ($1 \le l_i < r_i \le n$).

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

В ответ на каждый запрос выведите одно число – количество способов выбрать индексы $a$ и $b$ так, что что $l \le a < b \le r$, а скобочки с $a$-ой по $b$-ую образуют правильную скобочную последовательность.

Подзадачи