Условие этой задачи совпадает с задачей F. Отличия от задачи F подчеркнуты.

Вам дана строка $S$ длины $N$, состоящая только из символов ( и ).

Ответьте на $Q$ запросов. В $i$-м запросе вам даны целые числа $L_i$ и $R_i$. Решите следующую задачу:

Пусть $X$ — подстрока строки $S$ с $L_i$-го по $R_i$-й символ. Рассмотрим выбор положительного целого числа $k$, а затем выбор подстроки $Y$ строки, полученной конкатенацией $k$ копий $X$. Здесь $Y$ должна быть правильной скобочной последовательностью. $Y$ может быть пустой строкой.

Определите, существует ли максимально возможная длина для $Y$, и если существует, найдите это максимальное значение.

Правильная скобочная последовательность

Правильная скобочная последовательность — это строка, которую можно свести к пустой строке путем многократного удаления непрерывной подстроки () ноль или более раз.

Входные данные

Входные данные подаются из стандартного потока ввода в следующем формате:

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$-й строке выведите максимально возможную длину $Y$ для $i$-го запроса, если она существует, и -1 в противном случае.

Пример

Пример ввода 1

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

Пример вывода 1

-1
2
0

Примечание

• В первом запросе $X =$ )(. Для любого положительного целого числа $k$, если сконкатенировать $k$ копий $X$ и удалить первый и последний символы, получится правильная скобочная последовательность длины $2k - 2$. Следовательно, максимально возможной длины для $Y$ не существует, поэтому следует вывести -1.
• Во втором запросе $X =$ ()((. Можно доказать, что максимально возможная длина $Y$ равна $2$. Следовательно, выведите 2.
• В третьем запросе $X =$ ((. Максимально возможная длина $Y$ равна $0$, поэтому выведите 0. Обратите внимание, что $Y$ может быть пустой строкой.