配点 : 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 也可以是空字符串。