This is an interactive problem (a problem where your program and the judge system interact via input and output).
An integer sequence is called a non-zero sequence if it satisfies both of the following conditions:
- Any two elements are distinct.
- The sum of any non-empty (not necessarily contiguous) subsequence is not equal to $0$.
For example, $(5)$, $(1, -2, 3)$, and $(-3, 7, 5, -6)$ are non-zero sequences, while $(0)$, $(1, -3, 1)$, $(2, 3, -2)$, and $(1, 2, 3, -4)$ are not.
You are given positive integers $N$ and $X$.
Output, one by one from the beginning, the elements of a non-zero sequence $(A_1, A_2, \dots, A_X)$ of length $X = 2\lfloor\sqrt{N}\rfloor - 1$, consisting of integers between $-N$ and $N$ (inclusive). However, the sign of each element is specified immediately before it is output.
You are given $R$ test cases; interact with the judge for each of them.
Input
- $1 \le R \le 10^4$
- $1 \le N \le 10^4$
- $X = 2\lfloor\sqrt{N}\rfloor - 1$
- The sum of $N$ over all test cases does not exceed $10^4$
Interaction Protocol
First, the number of test cases $R$ is given in the following format:
R
Then, the following interaction is repeated $R$ times.
For each test case, positive integers $N$ and $X$ are given in the following format:
N X
After that, for each $i = 1, 2, \dots, X$ in this order, perform the following interaction.
First, the sign $op_i$ of $A_i$ is given in the following format:
op_i
$op_i$ is one of + or -, with the following meanings:
- If $op_i = \text{+}$, then $A_i$ must be a positive integer.
- If $op_i = \text{-}$, then $A_i$ must be a negative integer.
Then, output an integer $A_i$ between $-N$ and $N$ (inclusive) with the specified sign, on one line (you do not need to print a plus sign for positive integers):
A_i
Note
After each output, your program must flush standard output; otherwise, you will receive Time Limit Exceeded.
Example
Sample Input 1
2 4 3 - - + 3 1 +
Sample Output 1
-4 -1 2 3
Note
The sample interaction proceeds as follows:
| Input | Output | Explanation |
|---|---|---|
2 |
The number of test cases $R$ is given. | |
4 3 |
$N, X$ for the first test case are given. | |
- |
Since $op_1 = \text{-}$, $A_1$ must be a negative integer. | |
-4 |
You output $A_1 = -4$. | |
- |
Since $op_2 = \text{-}$, $A_2$ must be a negative integer. | |
-1 |
You output $A_2 = -1$. | |
+ |
Since $op_3 = \text{+}$, $A_3$ must be a positive integer. | |
2 |
You output $A_3 = 2$. Since $(A_1, A_2, A_3) = (-4, -1, 2)$ is a non-zero sequence, this test case is judged correct. | |
3 1 |
$N, X$ for the second test case are given. | |
+ |
Since $op_1 = \text{+}$, $A_1$ must be a positive integer. | |
3 |
You output $A_1 = 3$. Since $(A_1) = (3)$ is a non-zero sequence, this test case is judged correct. |