Problem Statement

This is an interactive problem (where your program interacts with the judge via input and output).

You are given a positive integer $N$.

The judge has a hidden positive integer $R$ and $N$ integers $A_1, A_2, \dots, A_N$. It is guaranteed that $|A_i|\le R$ and $\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R$.

There is a blackboard on which you can write integers with absolute values not exceeding $R$. Initially, the blackboard is empty.

The judge has written the values $A_1, A_2, \dots, A_N$ on the blackboard in this order. Your task is to make the blackboard contain only one value $\displaystyle\sum_{i=1}^{N}A_i$.

You cannot learn the values of $R$ and $A_i$ directly, but you can interact with the judge up to $25000$ times.

For a positive integer $i$, let $X_i$ be the $i$-th integer written on the blackboard. Specifically, $X_i = A_i$ for $i=1,2,\dots,N$.

In one interaction, you can specify two distinct positive integers $i$ and $j$ and choose one of the following actions:

• Perform addition. The judge will erase $X_i$ and $X_j$ from the blackboard and write $X_i + X_j$ on the blackboard.
• $|X_i + X_j| \leq R$ must hold.
• Perform comparison. The judge will tell you whether $X_i < X_j$ is true or false.

Here, at the beginning of each interaction, the $i$-th and $j$-th integers written on the blackboard must not have been erased.

Perform the interactions appropriately so that after all interactions, the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$.

The values of $R$ and $A_i$ are determined before the start of the conversation between your program and the judge.

Constraints

• $2 \leq N \leq 1000$
• $1 \leq R \leq 10^9$
• $|A_i| \leq R$
• $\left|\displaystyle\sum_{i=1}^{N}A_i\right| \le R$
• $N$, $R$, and $A_i$ are integers.

Input and Output

This is an interactive problem (where your program interacts with the judge via input and output).

First, read $N$ from Standard Input.

N

Next, repeat the interactions until the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$.

When performing addition, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

+ i j

The response from the judge will be given from Standard Input in the following format:

P

Here, $P$ is an integer:

• If $P \geq N + 1$, it means that the value $X_i + X_j$ has been written on the blackboard, and it is the $P$-th integer written.
• If $P = -1$, it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$.

When performing comparison, make an output in the following format to Standard Output. Append a newline at the end. Here, $i$ and $j$ are distinct positive integers.

? i j

The response from the judge will be given from Standard Input in the following format:

Q

Here, $Q$ is an integer:

• If $Q = 1$, it means that $X_i < X_j$ is true.
• If $Q = 0$, it means that $X_i < X_j$ is false.
• If $Q = -1$, it means that $i$ and $j$ do not satisfy the constraints, or the number of interactions has exceeded $25000$.

For both types of interactions, if the judge's response is $-1$, your program is already considered incorrect. In this case, terminate your program immediately.

When the blackboard contains only one value $\displaystyle\sum_{i=1}^{N}A_i$, report this to the judge in the following format. This does not count towards the number of interactions. Then, terminate your program immediately.

!

If you make an output in a format that does not match any of the above, -1 will be given from Standard Input.

-1

In this case, your program is already considered incorrect. Terminate your program immediately.

Note

• For each output, append a newline at the end and flush Standard Output. Otherwise, the verdict may be TLE.
• Terminate your program immediately after outputting the result (or receiving -1). Otherwise, the verdict will be indeterminate.
• Extra newlines will be considered as malformed output.

Sample Input and Output

Here is a possible conversation with $N=3, R=10, A_1=-1, A_2=10, A_3=1$.