This is an interactive problem.

After arriving in Country P under the guidance of an insider, you prepare to participate in the Pre-SDOI Training Camp (also known as Public Easy Round #2) warm-up contest. During the warm-up, you encounter the following problem:

• Given $n$ operators $\operatorname{op}_1, \operatorname{op}_2, \dots, \operatorname{op}_n$. For $n+1$ input integers $a_0, a_1, \dots, a_n$, you need to calculate the value of the following expression:

$$\bigg(\ldots\Big(\big((a_0 \,\operatorname{op}_1\, a_1) \,\operatorname{op}_2\, a_2\big) \,\operatorname{op}_3\, a_3\Big) \ldots \,\operatorname{op}_n\, a_n\bigg)\quad \bmod (10^9+7)$$

• For any $0 \leq i \leq n$, $0 \leq a_i < 10^9+7$.
• For any $1 \leq i \leq n$, $\operatorname{op}_i \in \{+, \times \}$, meaning each operator is either addition or multiplication.

You quickly wrote a program to solve this problem. Unfortunately, due to your excitement after solving it, you accidentally deleted the problem statement and your code, losing the information about the $n$ operators $\operatorname{op}_1, \operatorname{op}_2, \dots, \operatorname{op}_n$. Fortunately, the program you just compiled still exists, so you can recover these operators by querying your program.

Since the contest is about to end and your program is not very efficient, the number of queries you make to the program cannot exceed $Q_{\mathrm{max}} = 600$.

Implementation Details

This is an interactive problem. Only C++ is supported.

You need to submit a program operator that includes the header operator.h and implements the following function:

std::vector <int> solve(int n)

• In each test case, this function will be called exactly once during the program's execution.
• n represents the number of operators.
• It must return an array $O_0, O_1, \dots, O_{n-1}$ of length exactly $n$, representing the recovered operators $\operatorname{op}_i$.
  • You must ensure $O_i \in \{0, 1\}$.
  • $O_i = 0$ indicates that the recovered operator $\operatorname{op}_{i+1}$ is addition +.
  • $O_i = 1$ indicates that the recovered operator $\operatorname{op}_{i+1}$ is multiplication ×.

You can query the interactor by calling the following function:

int query(std::vector <int> a)

• In each test case, you may call this function at most $Q_{\mathrm{max}}$ times.
• a represents the $a_0, a_1, \dots, a_n$ you are querying.
  • You must ensure a.size() is exactly $n+1$, and $0 \leq a_i < 10^9+7$.
• This function will return a value in $[0, 10^9+7)$, describing the result of the query modulo $10^9+7$.

It is guaranteed that during the final evaluation, for any valid interaction process, the interactor will not exceed 0.2 seconds of time and 8 MiB of memory.

Examples

The provided files include a sample interactor grader.cpp, which can help you understand the problem and test your program. During the final evaluation, the interactor used will differ from this sample interactor; your program should not rely on the implementation of the sample interactor.

You can compile the executable answer using the following command:

g++ grader.cpp operator.cpp -o answer -O2

The executable answer will read input data from standard input in the following format:

• The first line of input contains an integer $n$.
• The next line contains $n$ integers $O_1, O_2, \dots, O_n$, describing each operator in the same format as the return value of the query function.

If your return value is correct, the executable will output a single integer to standard output, representing the number of queries you performed.

Interaction

During the final evaluation, the interactor and your program will run in two different processes, communicating via standard input and output. Therefore, your program should not read any information from standard input, nor should it output any information to standard output. You should also avoid using functions like std::ios::sync_with_stdio(false) or std::cin.tie(nullptr), as this may lead to unexpected errors.

Subtasks

For all data, $1 \leq n \leq 600$.

Let $Q$ be the number of queries performed by your program:

• If your program exceeds the time or memory limits, encounters a runtime error, or returns an incorrect answer, the score is $0$.
• Otherwise, your score depends on the number of queries $Q$:
  • If $Q \leq 40$, the score is $7$.
  • If $40 < Q \leq 43$, the score is $7 - (Q - 40)$.
  • If $43 < Q \leq 60$, the score is $3$.
  • If $60 < Q \leq 188$, the score is $2$.
  • If $188 < Q \leq 600$, the score is $1$.
  • Otherwise, the score is $0$.

Note

If you wish to use Hack after the contest, please note that the input format used by the interactor during final evaluation is different.

Please use the following input format to provide Hack data:

• The first line of input contains an integer $N$.
• The next line contains a string $S$ of length $N$ consisting only of + and x, describing each operator. + represents addition +, and x represents multiplication ×.