L'impostazione di questo problema è la stessa del Problema F. Le differenze rispetto al Problema F sono sottolineate.

Ti viene data una stringa $S$ di lunghezza $N$ composta solo da ( e ).

Rispondi a $Q$ query. Nella $i$-esima query ti vengono dati gli interi $L_i$ e $R_i$. Risolvi il seguente problema:

Sia $X$ la sottostringa di $S$ dal $L_i$-esimo carattere al $R_i$-esimo carattere. Considera di scegliere un intero positivo $k$ e poi di scegliere una sottostringa $Y$ della stringa ottenuta concatenando $k$ copie di $X$. Qui, $Y$ deve essere una sequenza di parentesi regolare. È consentito che $Y$ sia una stringa vuota.

Determina se esiste una lunghezza massima possibile per $Y$ e, se esiste, trova tale valore massimo.

Sequenza di parentesi regolare

Una sequenza di parentesi regolare è una stringa che può essere ridotta a una stringa vuota rimuovendo ripetutamente la sottostringa contigua () zero o più volte.

Input

L'input è fornito dallo Standard Input nel seguente formato:

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

• $N, Q, L_i, R_i$ sono interi.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ è una stringa di lunghezza $N$ composta solo da ( e ).
• $1 \le L_i \le R_i \le N$

Output

Stampa $Q$ righe. Per la $i$-esima riga, stampa la lunghezza massima possibile di $Y$ per la $i$-esima query se esiste, e -1 altrimenti.

Esempio

Input di esempio 1

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

Output di esempio 1

-1
2
0

Nota

• Nella prima query, $X =$ )(. Per qualsiasi intero positivo $k$, se concateniamo $k$ copie di $X$ e rimuoviamo il primo e l'ultimo carattere, otteniamo una sequenza di parentesi regolare di lunghezza $2k - 2$. Pertanto, non esiste una lunghezza massima possibile per $Y$, quindi devi stampare -1.
• Nella seconda query, $X =$ ()((. Si può dimostrare che la lunghezza massima possibile di $Y$ è $2$. Pertanto, stampa 2.
• Nella terza query, $X =$ ((. La lunghezza massima possibile di $Y$ è $0$, quindi stampa 0. Nota che $Y$ può essere una stringa vuota.