AT_utpc2025_f Finite Bracket Sequence

本問の設定は [G 問題](https://atcoder.jp/contests/utpc2025/tasks/utpc2025_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 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行にわたって出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリについて、 $ Y $ の長さとしてありうる最大値が存在するならば `Finite` を、存在しないならば `Infinite` を出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ X = $ `)(` です。任意の正整数 $ k $ に対し、 $ X $ を $ k $ 回連結した文字列から最初の文字と最後の文字を削除して得られる長さ $ 2k-2 $ の文字列は正しい括弧列であるため、 $ Y $ の長さとしてありうる最大値は存在しません。したがって、`Infinite` を出力します。 $ 2 $ 番目のクエリでは、 $ X = $ `()((` です。 $ Y $ の長さとしてありうる最大値は $ 2 $ であることが証明できます。したがって、`Finite` を出力します。 $ 3 $ 番目のクエリでは、 $ X = $ `((` です。 $ Y $ の長さとしてありうる最大値は $ 0 $ であるため、`Finite` を出力します。 $ Y $ は空文字列でもよいことに注意してください。 ### Constraints - $ N, Q, L_i, R_i $ は整数 - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ S $ は `(` および `)` のみからなる長さ $ N $ の文字列 - $ 1 \leq L_i \leq R_i \leq N $