C. Сережа и скобочки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Сережи есть скобочная последовательность s1, s2, ..., sn, или, другими словами, строка s длины n, состоящая из символов «(» и «)».

Сереже нужно ответить на m запросов, каждый из которых характеризуется двумя целыми числами li, ri (1 ≤ li ≤ ri ≤ n). Ответом на i-ый запрос является длина наибольшей правильной скобочной подпоследовательности последовательности sli, sli + 1, ..., sri. Помогите Сереже ответить на все запросы.

Определения подпоследовательности и правильной скобочной последовательности смотрите в примечаниях.

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

Первая строка содержит последовательность символов без пробелов s1, s2, ..., sn (1 ≤ n ≤ 106). Каждый символ это либо «(», либо «)». Вторая строка содержит целое число m (1 ≤ m ≤ 105) количество запросов. Каждая из следующих m строк содержит пару целых чисел. В i-ой строке записаны числа li, ri (1 ≤ li ≤ ri ≤ n) — описание i-го запроса.

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

Выведите ответ на каждый запрос в отдельной строке. Ответы выводите в порядке следования запросов во входных данных.

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

Подпоследовательностью длины |x| строки s = s1s2... s|s| (где |s| — длина строки s) называется строка x = sk1sk2... sk|x| (1 ≤ k1 < k2 < ... < k|x| ≤ |s|).

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

Для третьего запроса искомая последовательность будет «()».

Для четвертого запроса искомая последовательность будет «()(())(())».