本题的背景与问题 G 相同。与问题 G 的不同之处用下划线标出。

给你一个长度为 $N$ 且仅由 ( 和 ) 组成的字符串 $S$。

回答 $Q$ 个询问。在第 $i$ 个询问中，给你整数 $L_i$ 和 $R_i$。解决以下问题：

设 $X$ 为 $S$ 从第 $L_i$ 个字符到第 $R_i$ 个字符的子串。考虑选择一个正整数 $k$，然后选择将 $k$ 个 $X$ 拼接后得到的字符串的一个子串 $Y$。这里，$Y$ 必须是一个合法括号序列。$Y$ 允许为空串。

判断 $Y$ 是否存在最大可能长度。

合法括号序列

一个合法括号序列是一个可以通过重复删除连续子串 () 零次或多次而缩减为空串的字符串。

输入格式

输入从标准输入按以下格式给出：

N Q
S
L1 R1
L2 R2
...
LQ RQ

数据范围

• $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$ 行，如果第 $i$ 个询问中 $Y$ 存在最大可能长度，则输出 Finite，否则输出 Infinite。

样例

样例输入 1

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

样例输出 1

Infinite
Finite
Finite

说明

• 在第一个询问中，$X = \text{)(}$。对于任意正整数 $k$，如果我们拼接 $k$ 个 $X$ 并删去首尾字符，就能得到一个长度为 $2k - 2$ 的合法括号序列。因此，$Y$ 不存在最大可能长度，所以你应该输出 Infinite。
• 在第二个询问中，$X = \text{()((}$。可以证明 $Y$ 的最大可能长度为 $2$。因此，输出 Finite。
• 在第三个询问中，$X = \text{((}$。$Y$ 的最大可能长度为 $0$，所以输出 Finite。注意 $Y$ 可以是空串。