{"problem":{"name":"Magician","description":{"content":"**This is an interactive problem.** There 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 lexicog","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc072_d"},"statements":[{"statement_type":"Markdown","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* * *\n\n## Constraints\n\n*   $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.\n\n## Input And Output\n\nFirst, 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.)\n\n[samples]\n\n## Notes\n\n**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* * *","is_translate":false,"language":"English"}],"meta":{"iden":"agc072_d","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:13"}}