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.

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

Notes

Sample Interaction

Note that this is just an example of interaction.