Die Aufgabenstellung dieses Problems ist dieselbe wie bei Problem F. Die Unterschiede zu Problem F sind unterstrichen.

Gegeben ist eine Zeichenkette $S$ der Länge $N$, die nur aus ( und ) besteht.

Beantworte $Q$ Anfragen. In der $i$-ten Anfrage sind ganze Zahlen $L_i$ und $R_i$ gegeben. Löse das folgende Problem:

Sei $X$ die Teilzeichenkette von $S$ vom $L_i$-ten Zeichen bis zum $R_i$-ten Zeichen. Betrachte die Wahl einer positiven ganzen Zahl $k$ und anschließend die Wahl einer Teilzeichenkette $Y$ der Zeichenkette, die durch Aneinanderhängen von $k$ Kopien von $X$ entsteht. Dabei muss $Y$ eine korrekte Klammerfolge sein. $Y$ darf auch die leere Zeichenkette sein.

Bestimme, ob eine maximal mögliche Länge für $Y$ existiert, und falls sie existiert, finde diesen Maximalwert.

Korrekte Klammerfolge

Eine korrekte Klammerfolge ist eine Zeichenkette, die durch wiederholtes Entfernen der zusammenhängenden Teilzeichenkette () (null- oder mehrmals) auf eine leere Zeichenkette reduziert werden kann.

Eingabe

Die Eingabe erfolgt über die Standardeingabe im folgenden Format:

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

• $N, Q, L_i, R_i$ sind ganze Zahlen.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ ist eine Zeichenkette der Länge $N$, die nur aus ( und ) besteht.
• $1 \le L_i \le R_i \le N$

Ausgabe

Gib $Q$ Zeilen aus. Gib in der $i$-ten Zeile die maximal mögliche Länge von $Y$ für die $i$-te Anfrage aus, falls sie existiert, und andernfalls -1.

Beispiel

Beispieleingabe 1

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

Beispielausgabe 1

-1
2
0

Hinweis

• In der ersten Anfrage ist $X =$ )(. Wenn wir für eine beliebige positive ganze Zahl $k$ genau $k$ Kopien von $X$ aneinanderhängen und das erste sowie das letzte Zeichen entfernen, erhalten wir eine korrekte Klammerfolge der Länge $2k - 2$. Daher gibt es keine maximal mögliche Länge für $Y$, sodass du -1 ausgeben solltest.
• In der zweiten Anfrage ist $X =$ ()((. Es lässt sich beweisen, dass die maximal mögliche Länge von $Y$ gleich $2$ ist. Gib daher 2 aus.
• In der dritten Anfrage ist $X =$ ((. Die maximal mögliche Länge von $Y$ ist $0$, gib also 0 aus. Beachte, dass $Y$ eine leere Zeichenkette sein kann.