Problem H
Crusaders of the Lost Mark

Apple Bloom, Sweetie Belle and Scootaloo are trying to discover their calling, and so they are trying various things to see what they are good at. Today, they decided to help ponies find suitable housing. They need to process the applications of ponies who want to settle down in the kingdom, and give suggestions based on their monthly income.

There are $A$ applications to process; the $i^\text {th}$ application contains $S_ i$, the monthly income of the $i^\text {th}$ applicant. For each application, they want to determine the best city to live that they can afford; that is, the city whose monthly cost of living is largest but still not exceeding their monthly income. It is guaranteed that each pony has at least one city they can afford to live in.

There are $C$ cities in Equestria, labelled $1, 2, \dots , C$, with costs of living $R_1, R_2, \dots , R_ C$, respectively. They don’t actually know the values of $R$; they only know that for all positive integers $i < C$, it holds $R_ i < R_{i+1}$.

They can call the national housing board to find out the cost of living in a particular city, but they have to pay an administrative fee of $\$ 1$ each time.

They only have $\$ 1\, 500$. Without exceeding their budget, help them determine where each pony should live!

Interaction

First, your program should read two integers $C$ $(1 \leq C \leq 10^6)$ and $A$ $(1 \leq A \leq 106)$, the number of cities and the number of applications, respectively, on a single line from standard input.

Then, your program should read $A$ integers $S_1, S_2, \dots , S_ A$ $(R_1 \leq S_ i \leq 10^9)$, the monthly incomes of each pony, on a single line from standard input.

Then, we repeat the following process:

• Your program writes a single line to the standard output in either format:

  • $\texttt{Q}\: c$ ($1 \leq c \leq C$), meaning that they should spend $\$ 1$ to ask for the monthly cost of living in city $c$. Obviously, they can only do this if they have a positive number of dollars left.

  • $\texttt{A}\: P_1\: P_2\: \dots \: P_ A$ ($1 \leq P_ i \leq C$), meaning that they should suggest pony $i$ to live in city $P_ i$.

• If your program asks a question, your program should read $R_ c$ $(1 \leq R_ c \leq 10^9)$ from standard input.

• If your program guesses the answer, your answer will be checked. Your program should terminate immediately after this.

After asking each question, do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python;

• see documentation for other languages.

Sample interaction