Problem Statement

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.

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.

Input and Output

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.)

Note

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.