Latar belakang masalah ini sama dengan Masalah F. Perbedaan dari Masalah F digarisbawahi.

Anda diberikan sebuah string $S$ dengan panjang $N$ yang hanya terdiri dari ( dan ).

Jawablah $Q$ kueri. Pada kueri ke-$i$, Anda diberikan bilangan bulat $L_i$ dan $R_i$. Selesaikan masalah berikut:

Misalkan $X$ adalah substring dari $S$ mulai dari karakter ke-$L_i$ hingga karakter ke-$R_i$. Pertimbangkan untuk memilih sebuah bilangan bulat positif $k$ lalu memilih sebuah substring $Y$ dari string yang diperoleh dengan menggabungkan $k$ salinan dari $X$. Di sini, $Y$ harus berupa barisan tanda kurung yang valid. $Y$ diperbolehkan berupa string kosong.

Tentukan apakah ada panjang maksimum yang mungkin untuk $Y$, dan jika ada, carilah nilai maksimum tersebut.

Barisan Tanda Kurung yang Valid

Barisan tanda kurung yang valid adalah string yang dapat direduksi menjadi string kosong dengan menghapus substring berurutan () secara berulang nol kali atau lebih.

Masukan

Masukan diberikan dari Masukan Standar dalam format berikut:

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

• $N, Q, L_i, R_i$ adalah bilangan bulat.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ adalah string dengan panjang $N$ yang hanya terdiri dari ( dan ).
• $1 \le L_i \le R_i \le N$

Keluaran

Cetak $Q$ baris. Untuk baris ke-$i$, cetak panjang maksimum yang mungkin dari $Y$ untuk kueri ke-$i$ jika ada, dan -1 jika sebaliknya.

Contoh

Contoh Masukan 1

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

Contoh Keluaran 1

-1
2
0

Catatan

• Pada kueri pertama, $X =$ )(. Untuk setiap bilangan bulat positif $k$, jika kita menggabungkan $k$ salinan dari $X$ dan menghapus karakter pertama dan terakhir, kita memperoleh barisan tanda kurung yang valid dengan panjang $2k - 2$. Oleh karena itu, tidak ada panjang maksimum yang mungkin untuk $Y$, sehingga Anda harus mencetak -1.
• Pada kueri kedua, $X =$ ()((. Dapat dibuktikan bahwa panjang maksimum yang mungkin dari $Y$ adalah $2$. Oleh karena itu, cetak 2.
• Pada kueri ketiga, $X =$ ((. Panjang maksimum yang mungkin dari $Y$ adalah $0$, sehingga cetak 0. Perhatikan bahwa $Y$ dapat berupa string kosong.