この問題の設定は問題 G と同じです。問題 G との相違点には下線が引かれています。

( と ) のみからなる長さ $N$ の文字列 $S$ が与えられます。

$Q$ 個のクエリに答えてください。$i$ 番目のクエリでは、整数 $L_i$ と $R_i$ が与えられます。次の問題を解いてください：

$S$ の $L_i$ 文字目から $R_i$ 文字目までの部分文字列を $X$ とします。正の整数 $k$ を選び、$X$ を $k$ 個連結して得られる文字列の部分文字列 $Y$ を選ぶことを考えます。ここで、$Y$ は正しい括弧列でなければなりません。$Y$ は空文字列であっても構いません。

$Y$ の長さとしてあり得る最大値が存在するかどうかを判定してください。

正しい括弧列

正しい括弧列とは、連続する部分文字列 () を $0$ 回以上繰り返し削除することで空文字列にできる文字列のことです。

入力

入力は以下の形式で標準入力から与えられます：

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$ 行目には、$i$ 番目のクエリにおいて $Y$ の長さの最大値が存在するならば Finite を、存在しないならば Infinite を出力してください。

入出力例

入力例 1

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

出力例 1

Infinite
Finite
Finite

注記

• $1$ 番目のクエリでは、$X =$ )( です。任意の正の整数 $k$ に対して、$X$ を $k$ 個連結して先頭と末尾の文字を取り除くと、長さ $2k - 2$ の正しい括弧列が得られます。したがって、$Y$ の長さの最大値は存在しないため、Infinite を出力します。
• $2$ 番目のクエリでは、$X =$ ()(( です。$Y$ の長さの最大値は $2$ であることが証明できます。したがって、Finite を出力します。
• $3$ 番目のクエリでは、$X =$ (( です。$Y$ の長さの最大値は $0$ であるため、Finite を出力します。$Y$ は空文字列でもよいことに注意してください。