This is an interactive problem.

In a distant land, people use a mysterious currency system. There are $n$ different types of currency in their system, with denominations $a_1, a_2, \dots, a_n$. You may assume that the quantity of each currency is infinite. Denominations that are smaller (i.e., $a_i \leq 10^3$) are called coins, and the number of such denominations is denoted by $n_1$. Denominations that are larger (i.e., $a_i > 10^3$) are called banknotes, and the number of such denominations is denoted by $n_2$. Due to local customs, some prices can be represented by a combination of these currencies, while others cannot.

You do not know the specific details of this currency system, including the values of $n$ and $a_i$. However, you can ask the locals whether a price $v$ can be represented by these currencies. Naturally, you need to determine $n$ and $a_i$ using as few queries as possible.

Since different sets of $n$ and $a_i$ might produce the same results, you only need to find one set of values that satisfies the query results. That is, for any $v$ within the queried range, your answer must be able to represent $v$ if and only if the interactive library's system can represent $v$.

Task

You need to implement a function solve to determine the specific values of $n$ and $a_i$ for this currency system.

• solve(type)
  • type is the data type of the test case; see "Subtasks" for details.

In each test case, the interactive library will call the solve function exactly once. Within this function, you need to call the query function to obtain information and the answer function to submit your result.

You can call the query function to ask whether a price can be represented by the currency, but the number of calls to this function cannot exceed $limit$.

• query(v)
  • v is the price you are querying, which must satisfy $0 \leq v \leq 10^{18}$.
  • This function returns $0$ or $1$, indicating whether $v$ can be represented.

You must call the answer function to submit your result, and this function must be called exactly once.

• answer(n, a)
  • n is the number of elements in your answer, which must satisfy $1 \leq n \leq 10^2$.
  • a is an array of size $n$, where the $i$-th element is $a_i$. The array is 0-indexed, and you must ensure $1 \leq a_i \leq 10^9$.

Implementation Details

You must submit a single source file currency.cpp that implements the above functions and follows the naming and interface conventions below.

The source code must include the header file currency.h.

The function solve you need to implement:

void solve(int type);

The interface for the query function is as follows:

bool query(long long v);

The interface for the answer function is as follows:

void answer(int n, int *a);

You can use the currency.cpp provided in the supplementary files as a template to start your program.

Interaction for Other Languages

Languages other than C/C++ can interact via standard input and output.

At the start of the program, read one line from standard input containing the integer <type>, representing the type of the test data.

Whenever you need to call query(), output a line Q <v> to standard output and flush the output buffer (e.g., flush(output) in Pascal, System.out.flush() in Java; please refer to language documentation for others). Then, read one line from standard input containing an integer $0$ or $1$ representing the result of the query.

When you need to call answer(), output two lines: the first line should be A <n>, and the second line should contain $n$ space-separated positive integers $a_1, a_2, \dots, a_n$.

All outputs must also satisfy the aforementioned constraints.

Subtasks

For $100\%$ of the test data, $1 \leq n \leq 10^2$ and $1 \leq a_i \leq 10^9$. The data in the interactive library is guaranteed to satisfy the constraints on $n_1$ and $n_2$, but the answer you submit does not necessarily have to satisfy these constraints.

How to Test Your Program (C/C++ Only)

g++ grader.cpp currency.cpp -o currency -O2

The executable will read data from standard input and output the results to standard output.

After reading is complete, the interactive library will call the solve function. If you call query more than $limit$ times, or call answer fewer or more than once, the interactive library will output an error message and terminate. If the arguments passed to query or answer are invalid, the interactive library will output a detailed error message and terminate.

When the answer function is called correctly and the solve function returns, the interactive library will determine whether your submitted answer meets the requirements. If the answer is correct, it will output Correct!; otherwise, it will output Incorrect!.

Adding -DDEBUG to the compilation command will cause the interactive library to output more debugging information.

If you wish to test with your own input files, please ensure the input file follows the format below; otherwise, the program's correct execution is not guaranteed.

The first line contains two integers $type, limit$, where $type \in \{1, 2, 3, 4, 5, 6\}$ and $0 \leq limit \leq 10^9$.

The second line contains an integer $n$, where $1 \leq n \leq 10^2$.

The third line contains $n$ integers, where the $i$-th number is $a_i$, satisfying $1 \leq a_i \leq 10^9$ and the constraints on $n_1$ and $n_2$ for the given $type$.

Please note that the currency.h used for final evaluation is different from the one provided.