Treść tego zadania jest taka sama jak Zadania F. Różnice względem Zadania F zostały podkreślone.

Dany jest napis $S$ o długości $N$, składający się wyłącznie ze znaków ( oraz ).

Odpowiedz na $Q$ zapytań. W $i$-tym zapytaniu dane są liczby całkowite $L_i$ oraz $R_i$. Rozwiąż następujący problem:

Niech $X$ będzie podciągiem spójnym (podnapisem) napisu $S$ od $L_i$-tego znaku do $R_i$-tego znaku. Rozważmy wybranie dodatniej liczby całkowitej $k$, a następnie wybranie podnapisu $Y$ napisu powstałego przez sklejenie $k$ kopii $X$. Tutaj $Y$ musi być poprawnym ciągiem nawiasowym. $Y$ może być napisem pustym.

Rozstrzygnij, czy istnieje maksymalna możliwa długość napisu $Y$, a jeśli istnieje, wyznacz tę maksymalną wartość.

Poprawny ciąg nawiasowy

Poprawny ciąg nawiasowy to napis, który można zredukować do napisu pustego poprzez wielokrotne (zero lub więcej razy) usuwanie spójnego podnapisu ().

Wejście

Wejście jest podawane ze standardowego wejścia w następującym formacie:

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

• $N, Q, L_i, R_i$ są liczbami całkowitymi.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ jest napisem o długości $N$ składającym się wyłącznie z ( oraz ).
• $1 \le L_i \le R_i \le N$

Wyjście

Wypisz $Q$ wierszy. W $i$-tym wierszu wypisz maksymalną możliwą długość $Y$ dla $i$-tego zapytania, jeśli istnieje, lub -1 w przeciwnym przypadku.

Przykład

Przykładowe wejście 1

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

Przykładowe wyjście 1

-1
2
0

Uwaga

• W pierwszym zapytaniu $X =$ )(. Dla dowolnej dodatniej liczby całkowitej $k$, jeśli skleimy $k$ kopii $X$ i usuniemy pierwszy oraz ostatni znak, otrzymamy poprawny ciąg nawiasowy o długości $2k - 2$. Zatem nie istnieje maksymalna możliwa długość dla $Y$, więc należy wypisać -1.
• W drugim zapytaniu $X =$ ()((. Można udowodnić, że maksymalna możliwa długość $Y$ wynosi $2$. Zatem wypisz 2.
• W trzecim zapytaniu $X =$ ((. Maksymalna możliwa długość $Y$ wynosi $0$, więc wypisz 0. Zauważ, że $Y$ może być napisem pustym.