Bracket Game

AtCoder

IDarc209_a

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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

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.

API Response (JSON)

{
  "problem": {
    "name": "Bracket Game",
    "description": {
      "content": "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 foll",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc209_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a string $S$ consisting of `(` and `)`.\nTaro and Jiro will play the following game using this string.\nTaro goes first and Jiro goes second; they alternately choose and perform one of the foll...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments