分数: 700 点
问题陈述
有一个字符串 S 组成 ( 和 ).
太郎和次郎将使用该字符串玩以下游戏。
太郎第一,二郎第二;他们交替选择并执行以下三种类型的操作之一:
- 删除第一个字符 S.
- 删除最后一个字符 S.
- 声明终止。
当长度达到 S 正好变成 K,或者当任一玩家宣布终止时。在游戏结束时,如果 S 是正确的括号序列,Jiro 获胜;否则,太郎获胜。
鉴于 S 比赛开始前,当双方都表现最佳时确定获胜者。
你被给予 T 测试用例。解决它们中的每一个。
什么是正确的括号序列?
正确的括号序列是可以通过重复删除子字符串的操作将字符串缩减为空字符串() 零次或多次。
约束
- 1 \le T \le 10^5
- 1 \le K < |S| \le 10^6
- S 是一个由以下组成的字符串
(和). - T 和 K 是整数。
- 总和 |S| 所有测试用例最多 10^6.
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
S K
输出
对于每个测试用例,打印 First 如果太郎获胜,并且 Second 如果二郎赢了。
示例输入 1
4 (()()) 2 (())() 2 (() 2 (()()())((()()(())())) 12
示例输出 1
Second First First First
对于第一个测试用例,以下是游戏如何进行的示例:
-
比赛开始前, S is
(()()). -
太郎删除第一个字符 S,导致
()()). -
接下来,Jiro 删除了最后一个字符 S,导致
()(). -
接下来,太郎删除了最后一个字符 S,导致
()(. -
接下来,Jiro 删除了最后一个字符 S,导致
(),以及长度 S 变为 K=2,所以游戏结束。 -
决赛 S 是正确的括号序列,因此 Jiro 获胜。
例如,在第三个测试用例中,Taro 可以通过在第一回合宣布终止来获胜。