Умова цієї задачі збігається із задачею F. Відмінності від задачі F підкреслено.

Вам дано рядок $S$ довжини $N$, що складається лише із символів ( та ).

Дайте відповідь на $Q$ запитів. У $i$-му запиті вам дано цілі числа $L_i$ та $R_i$. Розв'яжіть таку задачу:

Нехай $X$ — підрядок рядка $S$ з $L_i$-го по $R_i$-й символ. Розглянемо вибір додатного цілого числа $k$, а потім вибір підрядка $Y$ рядка, отриманого конкатенацією $k$ копій $X$. Тут $Y$ має бути правильною дужковою послідовністю. $Y$ може бути порожнім рядком.

Визначте, чи існує максимально можлива довжина для $Y$, і якщо існує, знайдіть це максимальне значення.

Правильна дужкова послідовність

Правильна дужкова послідовність — це рядок, який можна звести до порожнього рядка шляхом багаторазового видалення неперервного підрядка () нуль або більше разів.

Вхідні дані

Вхідні дані подаються зі стандартного потоку вводу в такому форматі:

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

• $N, Q, L_i, R_i$ — цілі числа.
• $1 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $S$ — рядок довжини $N$, що складається лише з ( та ).
• $1 \le L_i \le R_i \le N$

Вихідні дані

Виведіть $Q$ рядків. У $i$-му рядку виведіть максимально можливу довжину $Y$ для $i$-го запиту, якщо вона існує, та -1 в іншому разі.

Приклад

Приклад вводу 1

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

Приклад виводу 1

-1
2
0

Примітка

• У першому запиті $X =$ )(. Для будь-якого додатного цілого числа $k$, якщо сконкатенувати $k$ копій $X$ і видалити перший та останній символи, ми отримаємо правильну дужкову послідовність довжини $2k - 2$. Отже, максимально можливої довжини для $Y$ не існує, тому слід вивести -1.
• У другому запиті $X =$ ()((. Можна довести, що максимально можлива довжина $Y$ дорівнює $2$. Отже, виведіть 2.
• У третьому запиті $X =$ ((. Максимально можлива довжина $Y$ дорівнює $0$, тому виведіть 0. Зауважте, що $Y$ може бути порожнім рядком.