A - Bracket Game Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

( と ) のみからなる文字列 S があります。

太郎君と次郎君はこの文字列を使って以下のゲームをします。

太郎君が先手、次郎君が後手となり、以下の 3 種類の操作のうちいずれか 1 つを選んで行うことを交互に繰り返します。

  • S の先頭の文字を削除する。
  • S の末尾の文字を削除する。
  • 終了宣言をする。

S の長さがちょうど K になったとき、あるいはいずれかのプレイヤーが終了宣言をした時点で、ゲームが終了します。ゲームの終了時点で S が正しい括弧列であるならば次郎君の勝利、そうでないならば太郎君の勝利となります。

ゲーム開始前の S が与えられるので、両者が最適に行動した場合の勝者を求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

正しい括弧列とは 正しい括弧列とは、() である部分文字列を削除することを 0 回以上繰り返して空文字列にできる文字列を指します。

制約

  • 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

1 つ目のテストケースについて、ありうるゲームの進行の例を示します。

  • ゲーム開始前の S は (()()) です。

  • 太郎君が S の先頭の文字を削除し ()()) となります。

  • 次に次郎君が S の末尾の文字を削除し ()() となります。

  • 次に太郎君が S の末尾の文字を削除し ()( となります。

  • 次に次郎君が S の末尾の文字を削除し () となり、S の長さが K=2 となったのでゲームが終了します。

  • 最終的な S は正しい括弧列なので次郎君の勝利となります。

3 つ目のテストケースでは例えば太郎君が最初のターンで終了宣言をすることで太郎君の勝利となります。

Score : 700 points

Problem Statement

There is a string S consisting of ( and ).

Taro and Jiro will play the following game using this string.

Taro goes first and Jiro goes second; they alternately choose and perform one of the following three types of operations:

  • Delete the first character of S.
  • Delete the last character of S.
  • Declare termination.

The game ends when the length of S becomes exactly K, or when either player declares termination. At the end of the game, if S is a correct bracket sequence, Jiro wins; otherwise, Taro wins.

Given S before the game starts, determine the winner when both players act optimally.

You are given T test cases. Solve each of them.

What is a correct bracket sequence? A correct bracket sequence is a string that can be reduced to an empty string by repeating the operation of deleting a substring () zero or more times.

Constraints

  • 1 \le T \le 10^5
  • 1 \le K < |S| \le 10^6
  • S is a string consisting of ( and ).
  • T and K are integers.
  • The sum of |S| over all test cases is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is given in the following format:

S
K

Output

For each test case, print First if Taro wins, and Second if Jiro wins.

Sample Input 1

4
(()())
2
(())()
2
(()
2
(()()())((()()(())()))
12

Sample Output 1

Second
First
First
First

For the first test case, here is an example of how the game might proceed:

  • Before the game starts, S is (()()).

  • Taro deletes the first character of S, resulting in ()()).

  • Next, Jiro deletes the last character of S, resulting in ()().

  • Next, Taro deletes the last character of S, resulting in ()(.

  • Next, Jiro deletes the last character of S, resulting in (), and the length of S becomes K=2, so the game ends.

  • The final S is a correct bracket sequence, so Jiro wins.

In the third test case, for example, Taro can win by declaring termination on the first turn.