시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 2 2 100.000%

문제

괄호 문자열은 다음과 같이 정의된다.

  1. 빈 문자열은 괄호 문자열이다.
  2. S가 괄호 문자열일 때, (S)도 괄호 문자열이다.
  3. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다.
  4. 모든 괄호 문자열은 위의 3개 규칙으로만 만들 수 있다.

'('와 ')'로 이루어진 문자열 S = s1s2...sN과 M개의 쿼리가 주어진다. 각각의 쿼리는 li와 ri(1 ≤ li ≤ ri ≤ n)로 이루어져 있다.  각각의 쿼리에 대해서 다음을 구해야 한다.

  • sli, sli+1, ..., sri로 이루어진 S의 부분 문자열 중에서 괄호 문자열 이면서 가장 긴 것의 길이를 출력한다.

문자열 S = s1s2...sN의 길이가 |x|인 부분 수열이란, 1 ≤ k1 < k2 < ..., K|x| ≤ N을 만족하는 문자열 x = sk1sk2...sk|x|를 의미한다.

입력

첫째 줄에 문자열 S가 주어진다. (1 ≤ N ≤ 1,000,000)

둘째 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

셋째 줄부터 M개의 줄에 쿼리 li와 ri가 주어진다.

출력

각각의 쿼리마다 정답을 출력한다.

예제 입력

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

예제 출력

0
0
2
10
4
6
6

힌트

출처