이 문제의 설정은 문제 F와 같습니다. 문제 F와의 차이점에는 밑줄이 그어져 있습니다.

(와 )로만 이루어진 길이 $N$의 문자열 $S$가 주어집니다.

$Q$개의 쿼리에 답하세요. $i$번째 쿼리에서는 정수 $L_i$와 $R_i$가 주어집니다. 다음 문제를 해결하세요:

$S$의 $L_i$번째 문자부터 $R_i$번째 문자까지의 부분 문자열을 $X$라고 합시다. 양의 정수 $k$를 선택하고, $X$를 $k$번 이어 붙여 얻은 문자열의 부분 문자열 $Y$를 선택하는 것을 생각합시다. 여기서 $Y$는 올바른 괄호 문자열이어야 합니다. $Y$는 빈 문자열일 수도 있습니다.

$Y$의 가능한 최대 길이가 존재하는지 판별하고, 존재한다면 그 최댓값을 구하세요.

올바른 괄호 문자열

올바른 괄호 문자열이란 연속된 부분 문자열 ()를 $0$번 이상 반복해서 제거하여 빈 문자열로 만들 수 있는 문자열입니다.

입력

입력은 표준 입력에서 다음 형식으로 주어집니다:

N Q
S
L_1 R_1
L_2 R_2
...
L_Q R_Q

• $N, Q, L_i, R_i$는 정수입니다.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$는 (와 )로만 이루어진 길이 $N$의 문자열입니다.
• $1 \le L_i \le R_i \le N$

출력

$Q$개의 줄을 출력하세요. $i$번째 줄에는 $i$번째 쿼리에서 $Y$의 가능한 최대 길이가 존재하면 그 값을 출력하고, 그렇지 않으면 -1을 출력하세요.

예제

예제 입력 1

4 3
()((
2 3
1 4
3 4

예제 출력 1

-1
2
0

노트

• 첫 번째 쿼리에서 $X =$ )(입니다. 임의의 양의 정수 $k$에 대해, $X$를 $k$번 이어 붙인 뒤 첫 번째 문자와 마지막 문자를 제거하면 길이 $2k - 2$인 올바른 괄호 문자열을 얻습니다. 따라서 $Y$의 가능한 최대 길이는 존재하지 않으므로, -1을 출력해야 합니다.
• 두 번째 쿼리에서 $X =$ ()((입니다. $Y$의 가능한 최대 길이는 $2$임을 증명할 수 있습니다. 따라서 2를 출력합니다.
• 세 번째 쿼리에서 $X =$ ((입니다. $Y$의 가능한 최대 길이는 $0$이므로, 0을 출력합니다. $Y$는 빈 문자열일 수 있음에 유의하세요.