AT_tupc2024_r Bracket Game

`(`, `)`, `?` からなる長さが偶数の文字列 $ S $ が与えられます。 あおばさんとひろせさんがゲームを行います。あおばさんが先手で、 $ S $ に `?` がある限り以下の操作を交互に行います。 - $ S $ の `?` である文字を $ 1 $ つ選び、`(` または `)` で置き換える。 $ S $ から `?` が無くなったとき、 $ S $ が正しい括弧列ならあおばさんの勝ち、そうでないならひろせさんの勝ちになります。 お互いに自分が勝つために最適な行動をとったとき、どちらが勝つか判定してください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えてください。 正しい括弧列とは 以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。 - 空文字列 - ある正しい括弧列 $ S $ が存在して、`(`, $ S $ , `)` をこの順に連結した文字列 - ある空でない正しい括弧列 $ S, T $ が存在して、 $ S,T $ をこの順に連結した文字列

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ S $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースについて、 あおばさんが勝つならば `First` 、ひろせさんが勝つならば `Second` を出力せよ。

### Universal Cup 参加者へ この問題は Universal Cup に収録される際に削除されます。そのため、Universal Cup に AtCoder での結果を使用する場合はこの問題以外を先に解くことをおすすめします。 ### Sample Explanation 1 $ 1 $ つ目のテストケースについて、ゲームの進行として以下のようなものが考えられます。 - 始め $ S $ は `(???` である。 - あおばさんが $ 4 $ 文字目の `?` を `)` で置き換える。 $ S $ は `(??)` になる。 - ひろせさんが $ 2 $ 文字目の `?` を `)` で置き換える。 $ S $ は `()?)` になる。 - あおばさんが $ 3 $ 文字目の `?` を `(` で置き換える。 $ S $ は `()()` になる。 - $ S $ に `?` が残っていないので操作は終了する。 $ S $ は正しい括弧列であるためあおばさんの勝ちとなる。 $ 1 $ つ目のテストケースでは、ひろせさんがどのように行動してもあおばさんが勝つことができます。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ 2\leq |S|\leq 10^6 $ - $ S $ は `(`, `)`, `?` からなる長さが偶数の文字列 - 一つの入力ファイルに含まれる $ |S| $ の総和は $ 10^6 $ 以下 - $ T $ は整数