The jury has a binary string $S$ of length $N$ consisting of the characters $\texttt{0}$ and $\texttt{1}$. It has $K \geq 1$ characters $\texttt{1}$.
You need to make exactly $N$ guesses on the value of $K$. After the $i$-th guess $G_i$, you will be given $S_i$ (the $i$-th character of $S$).
You win if there exists some $j$ ($1 \leq j \leq N$) such that $G_j = K$ and $S_j = \texttt{1}$. Find a way to win.
Input Format
- Begin by reading a line containing a single integer $N$. Afterwards, you should make exactly $N$ guesses.
- To make the $i$-th guess ($1 \leq i \leq N$), you should output a single integer $G_i$ ($1 \leq G_i \leq N$). In response, you should read in a single character — the $i$-th character of $S$.
- After exactly $N$ guesses, your program should exit the interaction protocol. Otherwise, you may receive any verdict.
After printing a guess, do not forget to output the end of line and flush the output.
The interactor is adaptive. That is, the string $S$ is not fixed before the interaction and can change depending on your guesses.
Constraints
- $1 \leq N \leq 5000$
- All characters of $S$ are $\texttt{0}$ or $\texttt{1}$.
- $1 \leq K \leq N$
Sample Input 1
5
0
1
0
1
0
Sample Output 1
5
4
2
2
3
Explanation
In the example $N=5$ and $S = \texttt{01010}$, so $K=2$. The interaction proceeds as follows.
$$ \begin{array}{ccc} i & \text{Guess (contestant)} & \text{Response (interactor)} \\ 1 & 5 & \texttt{0} \\ 2 & 4 & \texttt{1} \\ 3 & 2 & \texttt{0} \\ 4 & 2 & \texttt{1} \\ 5 & 3 & \texttt{0} \\ \end{array} $$
The contestant wins, since $G_4=K$ and $S_4=\texttt{1}$. Note that although the contestant won before all $N$ guesses, the programs are required to interact for all $N$ guesses. Also note that the contestant doesn't win at $i=3$, since $S_3 \neq \texttt{1}$ (even though $K$ is guessed correctly).
ConversionConversion EmoticonEmoticon