Le cadre de ce problème est le même que celui du Problème F. Les différences par rapport au Problème F sont soulignées.

On vous donne une chaîne de caractères $S$ de longueur $N$ composée uniquement de ( et ).

Répondez à $Q$ requêtes. Dans la $i$-ème requête, on vous donne deux entiers $L_i$ et $R_i$. Résolvez le problème suivant :

Soit $X$ la sous-chaîne de $S$ allant du $L_i$-ème caractère au $R_i$-ème caractère. On considère le choix d'un entier strictement positif $k$, puis le choix d'une sous-chaîne $Y$ de la chaîne obtenue en concaténant $k$ copies de $X$. Ici, $Y$ doit être une séquence de parenthèses régulière. $Y$ peut être une chaîne vide.

Déterminez s'il existe une longueur maximale possible pour $Y$, et si elle existe, trouvez cette valeur maximale.

Séquence de parenthèses régulière

Une séquence de parenthèses régulière est une chaîne qui peut être réduite à une chaîne vide en supprimant de manière répétée la sous-chaîne contiguë () zéro fois ou plus.

Entrée

L'entrée est donnée depuis l'entrée standard dans le format suivant :

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

• $N, Q, L_i, R_i$ sont des entiers.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ est une chaîne de longueur $N$ composée uniquement de ( et ).
• $1 \le L_i \le R_i \le N$

Sortie

Affichez $Q$ lignes. Pour la $i$-ème ligne, affichez la longueur maximale possible de $Y$ pour la $i$-ème requête si elle existe, et -1 sinon.

Exemple

Exemple d'entrée 1

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

Exemple de sortie 1

-1
2
0

Note

• Dans la première requête, $X =$ )(. Pour tout entier strictement positif $k$, si nous concaténons $k$ copies de $X$ et supprimons le premier et le dernier caractère, nous obtenons une séquence de parenthèses régulière de longueur $2k - 2$. Par conséquent, il n'y a pas de longueur maximale possible pour $Y$, vous devez donc afficher -1.
• Dans la deuxième requête, $X =$ ()((. On peut prouver que la longueur maximale possible de $Y$ est $2$. Par conséquent, affichez 2.
• Dans la troisième requête, $X =$ ((. La longueur maximale possible de $Y$ est $0$, donc affichez 0. Notez que $Y$ peut être une chaîne vide.