← 返回题目列表

AtCoder · utpc2025_f

F. 有限括号序列

中文机器翻译题面 查看原题

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