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

Вам дано рядок $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$-му рядку виведіть Finite, якщо в $i$-му запиті існує максимально можлива довжина для $Y$, та Infinite в іншому разі.

Приклад

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

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

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

Infinite
Finite
Finite

Примітка

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