20052번 - 괄호 문자열 ?

괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다.

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

'('와 ')'로 이루어진 괄호 문자열 S = s₁s₂...s_N과 M개의 쿼리가 주어진다. 쿼리는 두 정수 i, j (1 ≤ i ≤ j ≤ N)로 이루어져 있고, 쿼리가 의미하는 것은 다음과 같다.

• S의 부분 문자열 S_iS_i+1...S_j가 올바른 괄호 문자열이면 1, 아니면 0

모든 쿼리를 수행하고, 쿼리의 결과를 누적한 값을 구해보자.

첫째 줄에 문자열 S가 주어진다. 둘째 줄에 쿼리의 개수 M이 주어진다. 셋째 줄부터 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

쿼리의 결과를 누적한 값을 출력한다.

• 1 ≤ |S| ≤ 100,000
• 1 ≤ M ≤ 100,000