{"raw_statement":[{"iden":"problem statement","content":"**This is an interactive problem.**\nThere are $\\tbinom{2N}{N}$ cards numbered $1$ to $\\tbinom{2N}{N}$ on a desk. Card $i$ $(1 \\le i \\le \\tbinom{2N}{N})$ shows on its front the $i$‑th string in lexicographic order among the strings consisting of $N$ zeros and $N$ ones.\nExample For $N = 2$, the fronts of cards $1$, $2$, $3$, $4$, $5$, $6$ are `0011`, `0101`, `0110`, `1001`, `1010`, `1100`, respectively.  \n\nWitch Alice writes one of the first $N$ uppercase letters (for example, `A` or `B` if $N = 2$) on the back of each card, then performs the following **magic** $T$ times.\n\n> **A single magic**\n> \n> 1.  The host announces a letter $s$ among the first $N$ uppercase letters.\n> 2.  The host writes a length-$2N$ string of all `0` on the blackboard.\n> 3.  For $i = 1, 2, \\dots, N$ in this order, do the following. Here, $a_1, b_1, \\dots, a_N, b_N$ are distinct integers from $1$ to $2N$.\n>     *   First, the host tells Alice integers $a_i$ and $b_i$.\n>     *   Then, Alice chooses exactly one of the $a_i$\\-th and $b_i$\\-th characters of the string on the blackboard, and sets it to `1`.\n> 4.  Let $x$ be the final string on the blackboard. Exactly one card shows $x$ on its front; look at its back. The magic succeeds if and only if the letter on its back equals $s$.\n\nNote that Alice learns $a_{i+1}$ and $b_{i+1}$ only after choosing which of the $a_i$\\-th and $b_i$\\-th characters to set to `1`.\nImplement a strategy that makes all $T$ magics succeed. Now, let us begin.\n\n* * *"},{"iden":"constraints","content":"*   $2 \\le N \\le 10$\n*   $1 \\le T \\le 5\\,000$\n*   The letter $s$ is among the first $N$ uppercase letters.\n*   $1 \\le a_i < b_i \\le 2N$\n*   $a_1, b_1, a_2, b_2, \\dots, a_N, b_N$ are distinct.\n*   $a_1, b_1, a_2, b_2, \\dots, a_N, b_N, s$ are fixed before the interaction starts.\n*   $N, T, a_i, b_i$ are integers."},{"iden":"input and output","content":"First, read the integers $N$ and $T$ given from Standard Input in the following format:\n\n$N$ $T$\n\nNext, let $c_i$ be the letter written on the back of card $i$, and print those letters in the following format, followed by a newline. Here, $c_i$ must be among the first $N$ uppercase letters.\n\n$c_1 c_2 \\cdots c_{\\tbinom{2N}{N}}$\n\nNext, repeat the following process $T$ times. The $t$\\-th iteration $(1 \\leq t \\leq T)$ corresponds to the $t$\\-th magic.\n\n> Read the announced letter $s$ given in the following format:\n> \n> $s$\n> \n> Then, for $i = 1, 2, \\dots, N$ in this order, do the following.\n> \n> *   Read integers $a_i$ and $b_i$ given in the following format:\n> \n> $a_i$ $b_i$\n> \n> *   Print the chosen position $d$ in the following format, followed by a newline. Here, $d$ must be $a_i$ or $b_i$.\n> \n> $d$\n> \n> If your output was malformed or the previous magic failed, no more input such as $s$ or $(a_i, b_i)$ is given, but `-1` is given from Standard Input. In this case, exit immediately. (If you fail for the first time in the $T$\\-th magic, or your output was malformed for the first time at $i = N$ in the $T$\\-th magic, no more input follows.)"},{"iden":"notes","content":"**Flush after every output.** Otherwise, you may receive a TLE verdict.\nIf you read `-1`, exit immediately. If you do so, you will receive a WA verdict, but continuing leads to an indeterminate verdict. Unnecessary newlines may be seen as malformed.\nThe judge is **non‑adaptive**; the values $a_1, b_1, a_2, b_2, \\dots, a_N, b_N, s$ are fixed before the interaction starts, and will not be affected by your output.\n\n* * *"},{"iden":"sample interaction","content":"Note that this is just an example of interaction.\n\nInput\n\nOutput\n\nComment\n\n`2 2`\n\nThe integers $N$ and $T$ are given from Standard Input.\n\n`ABABAB`\n\nPrint letters for the backs of the six cards.\n\n`A`\n\nThe first magic begins.  \nThe host declares `A`.\n\n`1 2`\n\nThe host tells you $(a_1, b_1) = (1, 2)$.\n\n`2`\n\nSet the second character to `1`.\n\n`3 4`\n\nThe host tells you $(a_2, b_2) = (3, 4)$.\n\n`3`\n\nSet the third character to `1`.  \nThe final string is `0110`, and the card with `0110` on its front has `A` on the back, so the magic succeeds.\n\n`B`\n\nThe second magic begins.  \nThe host declars `B`.\n\n`1 3`\n\nThe host tells you $(a_1, b_1) = (1, 3)$.\n\n`1`\n\nSet the first character to `1`.\n\n`2 4`\n\nThe host tells you $(a_2, b_2) = (2, 4)$.\n\n`2`\n\nSet the second character to `1`.  \nThe final string is `1100`, and the card with `1100` on its front has `B` on the back, so the magic succeeds."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}