괄호 부분 문자열 쿼리

괄호 문자열을 다음과 같이 정의한다.

1. 빈 문자열은 괄호 문자열이다.
2. $S$가 괄호 문자열이면 $(S)$도 괄호 문자열이다.
3. $S$와 $T$가 괄호 문자열이면 $ST$도 괄호 문자열이다.
4. 괄호 문자열은 위 세 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 문자열 $S = s_1 s_2 \dots s_N$과 쿼리 $M$개가 주어진다. 각 쿼리는 두 정수 $l_i$, $r_i$ ($1 \le l_i \le r_i \le N$)로 이루어진다.

각 쿼리마다 부분 문자열 $s_{l_i} s_{l_i + 1} \dots s_{r_i}$의 부분 수열 중에서 괄호 문자열이면서 가장 긴 것의 길이를 구한다.

문자열 $S = s_1 s_2 \dots s_N$의 길이가 $|x|$인 부분 수열은 $1 \le k_1 < k_2 < \dots < k_{|x|} \le N$을 만족하는 문자열 $x = s_{k_1} s_{k_2} \dots s_{k_{|x|}}$을 뜻한다.

첫째 줄에 문자열 $S$가 주어진다. $S$는 '('와 ')'로만 이루어지고, 길이 $N$은 $1 \le N \le 10^6$을 만족한다.

둘째 줄에 쿼리의 개수 $M$이 주어진다. ($1 \le M \le 10^5$)

셋째 줄부터 $M$개의 줄에 걸쳐 각 쿼리의 $l_i$와 $r_i$가 공백을 사이에 두고 주어진다.

각 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.