AT_agc072_d [AGC072D] Magician

**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 lexicographic order among the strings consisting of $ N $ zeros and $ N $ ones. Example For $ N = 2 $ , the fronts of cards $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ , $ 5 $ , $ 6 $ are `0011`, `0101`, `0110`, `1001`, `1010`, `1100`, respectively. Witch 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. > **A single magic** > > 1. The host announces a letter $ s $ among the first $ N $ uppercase letters. > 2. The host writes a length- $ 2N $ string of all `0` on the blackboard. > 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 $ . > - First, the host tells Alice integers $ a_i $ and $ b_i $ . > - 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`. > 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 $ . Note 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`. Implement a strategy that makes all $ T $ magics succeed. Now, let us begin. --- ### Input & Output Format First, read the integers $ N $ and $ T $ given from Standard Input in the following format: > $ N $ $ T $ Next, 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. > $ c_1 c_2 \cdots c_{\tbinom{2N}{N}} $ Next, repeat the following process $ T $ times. The $ t $ -th iteration $ (1 \leq t \leq T) $ corresponds to the $ t $ -th magic. > Read the announced letter $ s $ given in the following format: > > > $ s $ > > Then, for $ i = 1, 2, \dots, N $ in this order, do the following. > > - Read integers $ a_i $ and $ b_i $ given in the following format: > > > $ a_i $ $ b_i $ > > - Print the chosen position $ d $ in the following format, followed by a newline. Here, $ d $ must be $ a_i $ or $ b_i $ . > > > $ d $ > > 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/A

N/A

### Notes **Flush after every output.** Otherwise, you may receive a TLE verdict. If 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. The 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. --- ### Sample Interaction Note that this is just an example of interaction. InputOutputComment `2 2`The integers $ N $ and $ T $ are given from Standard Input. `ABABAB`Print letters for the backs of the six cards. `A`The first magic begins. The host declares `A`. `1 2`The host tells you $ (a_1, b_1) = (1, 2) $ . `2`Set the second character to `1`. `3 4`The host tells you $ (a_2, b_2) = (3, 4) $ . `3`Set the third character to `1`. The final string is `0110`, and the card with `0110` on its front has `A` on the back, so the magic succeeds. `B`The second magic begins. The host declars `B`. `1 3`The host tells you $ (a_1, b_1) = (1, 3) $ . `1`Set the first character to `1`. `2 4`The host tells you $ (a_2, b_2) = (2, 4) $ . `2`Set the second character to `1`. The final string is `1100`, and the card with `1100` on its front has `B` on the back, so the magic succeeds. ### Constraints - $ 2 \le N \le 10 $ - $ 1 \le T \le 5\,000 $ - The letter $ s $ is among the first $ N $ uppercase letters. - $ 1 \le a_i < b_i \le 2N $ - $ a_1, b_1, a_2, b_2, \dots, a_N, b_N $ are distinct. - $ a_1, b_1, a_2, b_2, \dots, a_N, b_N, s $ are fixed before the interaction starts. - $ N, T, a_i, b_i $ are integers.