El planteamiento de este problema es el mismo que el del Problema F. Las diferencias con respecto al Problema F están subrayadas.

Se te da una cadena $S$ de longitud $N$ que consta únicamente de ( y ).

Responde a $Q$ consultas. En la $i$-ésima consulta, se te dan los enteros $L_i$ y $R_i$. Resuelve el siguiente problema:

Sea $X$ la subcadena de $S$ desde el $L_i$-ésimo carácter hasta el $R_i$-ésimo carácter. Considera elegir un entero positivo $k$ y luego elegir una subcadena $Y$ de la cadena obtenida al concatenar $k$ copias de $X$. Aquí, $Y$ debe ser una secuencia de paréntesis regular. Se permite que $Y$ sea una cadena vacía.

Determina si existe una longitud máxima posible para $Y$ y, si existe, halla dicho valor máximo.

Secuencia de paréntesis regular

Una secuencia de paréntesis regular es una cadena que puede reducirse a una cadena vacía eliminando repetidamente la subcadena contigua () cero o más veces.

Entrada

La entrada se proporciona desde la Entrada Estándar en el siguiente formato:

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

• $N, Q, L_i, R_i$ son enteros.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ es una cadena de longitud $N$ que consta únicamente de ( y ).
• $1 \le L_i \le R_i \le N$

Salida

Imprime $Q$ líneas. Para la $i$-ésima línea, imprime la longitud máxima posible de $Y$ para la $i$-ésima consulta si existe, y -1 en caso contrario.

Ejemplo

Entrada de ejemplo 1

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

Salida de ejemplo 1

-1
2
0

Nota

• En la primera consulta, $X =$ )(. Para cualquier entero positivo $k$, si concatenamos $k$ copias de $X$ y eliminamos el primer y el último carácter, obtenemos una secuencia de paréntesis regular de longitud $2k - 2$. Por lo tanto, no existe una longitud máxima posible para $Y$, así que debes imprimir -1.
• En la segunda consulta, $X =$ ()((. Se puede demostrar que la longitud máxima posible de $Y$ es $2$. Por lo tanto, imprime 2.
• En la tercera consulta, $X =$ ((. La longitud máxima posible de $Y$ es $0$, así que imprime 0. Observa que $Y$ puede ser una cadena vacía.