/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
本問の設定は 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, 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
入力
入力は以下の形式で標準入力から与えられる。
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
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 は空文字列でもよいことに注意してください。