配点 : {100} 点
致环球杯参赛者
当包含在 Universal Cup 中时,此问题将被删除。因此,当使用 AtCoder 结果进行 Universal Cup 时,我们建议先解决其他问题。 给出了
問題文
(, ), ? 组成长度为偶数的字符串 S 。
对于
青叶小姐和广濑先生进行游戏。青叶小姐先手, S 至
该值是 ? ,就交替进行以下操作。
是
- S 可以得到第
?的字符 当 1 选择(或 至少)。
S 减去 ? 消失时,
如果S 是正确的括号序列,则青叶女士获胜,否则广濑先生获胜。
请判定当双方为自己获胜而采取最佳行动时,谁会获胜。
T 测试用例,因此请逐一回答。
正确的括号序列是
满足以下任一条件的字符串定义为正确的括号序列。- 空文字列
- 一些正确的括号序列 S 存在,
由
(, S,)按此顺序连接而成的字符串 - 有效的非空括号序列 S, T 存在, 由 S,T 按此顺序连接而成的字符串
制約
- 1\leq T\leq 10^5
- 2\leq |S|\leq 10^6
- S 是
您也可以写
(,),?组成长度为偶数的字符串 - 包含在一个输入文件中的 |S| 的总和为 10^6 以下
- T 是一个整数
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出。 打印
S
出力
T 行。i 在线 i 第几个测试用例,如果青叶先生获胜 First 如果广濑先生获胜 Second 。
入力例 1
3 (??? (()()) ??????
出力例 1
First First Second
1 关于第几个测试用例,游戏的进行可以考虑如下情形。
- 开始 S 是
您也可以写
(???。 - 青叶先生 4 第几个字符
?该值应乘以)。S 是 您也可以写(??)。 - 广濑先生 2 第几个字符
?该值应乘以)。S 是 您也可以写()?)。 - 青叶先生 3 第几个字符
?该值应乘以(。S 是 您也可以写()()。 - S 至
该值是
?因为已经没有了,所以操作结束。S 是正确的括号序列,因此青叶先生获胜。
1 在第几个测试用例里,无论广濑先生如何行动,青叶先生都可以获胜。