괄호

괄호를 싫어하는 사람이 있을까?

사슈카는 $2N$개의 괄호로 이루어진 괄호 열 $S=s_1 s_2 \dots s_{2N}$을 발견했다. 여는 괄호와 닫는 괄호는 각각 $N$개이다. 그녀는 괄호 열의 어지러움을, 올바른 괄호 열로 만들기 위해 필요한 원소 교환 횟수의 최솟값으로 정의한다. 올바른 괄호 열은 다음 규칙을 따른다.

• 빈 열은 올바른 괄호 열이다.
• 비어 있지 않은 $S$는 올바른 괄호 열 $A$, $B$가 존재해서 $S=$(+A+)+B로 쓸 수 있을 때, 그때에만 올바른 괄호 열이다. 여기서 $+$는 이어 붙이기를 뜻한다.

사슈카는 $Q$개의 열 $T_1, T_2, \dots, T_Q$의 어지러움을 알고 싶어 한다. $i$번째 열 $T_i=s_{L_i} s_{L_i+1} \dots s_{R_i}$는 $S$에서 위치 $L_i$부터 $R_i$까지의 모든 원소로 이루어진다. 모든 $T_i$는 여는 괄호와 닫는 괄호의 개수가 같다. $Q$개의 질문에 답하는 프로그램 parentheses를 작성하라.

첫 줄에 세 정수 $N$, $Q$, $G$가 주어진다. 각각 열에 있는 여는 괄호의 개수, 질문의 개수, 이 테스트가 속한 서브태스크 번호이다. 둘째 줄에는 괄호 $s_1 s_2 \dots s_{2N}$이 주어진다. 마지막 $Q$개의 줄에는 $i$번째 질문의 위치를 나타내는 정수 $L_i$와 $R_i$가 한 줄에 하나씩 주어진다.

표준 출력에 한 줄에 하나씩 수를 출력한다. $i$번째 수는 $T_i$를 올바른 괄호 열로 만드는 데 필요한 교환 횟수의 최솟값이다.

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq L_i < R_i \leq 2 \times N$
• 모든 질문은 서로 다르다.