R - Bracket Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : {100} 点

Universal Cup 参加者へ

この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。

問題文

(, ), ? からなる長さが偶数の文字列 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 つ目のテストケースでは、ひろせさんがどのように行動してもあおばさんが勝つことができます。