Андрей любит строки, которые состоят из круглых скобок, но еще больше он любит заменять скобки на точки.
У него есть строка длины N, к которой он применяет M операций. Каждая операция задается двумя натуральными числами li и ri, в результате операции в подстроке slisli + 1, ..., sri самая длинная правильная скобочная подпоследовательность (далее ПСП) заменяется на точки (каждая скобочка заменяется на точку).
Андрей хочет себя проверить и просит вас помочь ему: подсчитать сколько скобок после каждой операции были заменены на точки.
Если в подстроке есть несколько ПСП максимальной длины, то выбирается наименьшая. Правило сравнения следующие: пусть a1, a2, ... , al — позиции открывающихся скобок первой ПСП, а c1, c2, ..., cl — позиции открывающихся скобок второй ПСП. Считается, что первая ПСП меньше второй, если существует k (1 ≤ k ≤ l), такое что ai = ci (1 ≤ i < k) и ak > ck.
Если позиции открывающихся скобок обоих ПСП совпали, то сравниваются позиции закрывающихся скобок по следующему правилу: пусть b1, b2, ..., bl — позиции закрывающихся скобок первой ПСП, а d1, d2, ..., dl — позиции закрывающихся скобок второй ПСП. Считается, что первая ПСП меньше второй, если существует k (1 ≤ k ≤ l), такое что bi = di (1 ≤ i < k) и bk < dk.
На первой строке задается исходная строка S длины N (1 ≤ N ≤ 5 × 105), которая состоит из открывающихся и закрывающихся круглых скобок.
На второй строке задается натуральное число M (1 ≤ M ≤ 5 × 105) — количество операций.
В следующих M строках задаются операции, каждая строка состоит из двух натуральных чисел li и ri (1 ≤ li ≤ ri ≤ N) — левая и правая граница подстроки соответственно.
Для каждой операции на отдельной строке выведите единственное число — число скобок, которые были заменены на точки.
(((())()))
3
4 9
2 8
1 10
4
2
4
