{"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 following three types of operations:\n\n*   Delete the first character of $S$.\n*   Delete the last character of $S$.\n*   Declare termination.\n\nThe 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.\nGiven $S$ before the game starts, determine the winner when both players act optimally.\nYou are given $T$ test cases. Solve each of them.\nWhat 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.\n\n## Constraints\n\n*   $1 \\le T \\le 10^5$\n*   $1 \\le K < |S| \\le 10^6$\n*   $S$ is a string consisting of `(` and `)`.\n*   $T$ and $K$ are integers.\n*   The sum of $|S|$ over all test cases is at most $10^6$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach case is given in the following format:\n\n$S$\n$K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc209_a","tags":[],"sample_group":[["4\n(()())\n2\n(())()\n2\n(()\n2\n(()()())((()()(())()))\n12","Second\nFirst\nFirst\nFirst\n\nFor the first test case, here is an example of how the game might proceed:\n\n*   Before the game starts, $S$ is `(()())`.\n    \n*   Taro deletes the first character of $S$, resulting in `()())`.\n    \n*   Next, Jiro deletes the last character of $S$, resulting in `()()`.\n    \n*   Next, Taro deletes the last character of $S$, resulting in `()(`.\n    \n*   Next, Jiro deletes the last character of $S$, resulting in `()`, and the length of $S$ becomes $K=2$, so the game ends.\n    \n*   The final $S$ is a correct bracket sequence, so Jiro wins.\n    \n\nIn the third test case, for example, Taro can win by declaring termination on the first turn."]],"created_at":"2026-03-03 11:01:14"}}