406002: GYM102215 H Missing Number

Thomas has an array of integers $$$a_1,~\ldots,~a_n$$$, and all the elements in this array are distinct and belong to the interval from $$$0$$$ to $$$n$$$. As you can see, one of the numbers from $$$0$$$ to $$$n$$$ is missing in this array.

You have to find this number. You can ask the $$$b$$$-th bit of the number $$$a_i$$$ no more than $$$2 \cdot n + 19$$$ times.

This is an interactive problem. Your program should communicate with the jury's program, using standard input and output for that.

In the beginning your program gets a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the array.

After that you can ask no more than $$$2 \cdot n + 19$$$ questions. To ask a question, output a character «?», and then after a space two integers $$$i$$$ and $$$b$$$ ($$$1 \le i \le n, 0 \le b \le \log_{2}n$$$) — the index $$$i$$$ in the array and the bit you want to know. Bits are numbered from zero, starting from the lowest.

As a response you will get an integer $$$0$$$ or $$$1$$$ — the value of the $$$b$$$-th bit of the number $$$a_i$$$.

When you determine the number missing in the array, output a character «!», and then after a space output this number. Then your program must terminate.

3

0

1

0

? 1 1

? 2 0

? 3 1

! 2

Please note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury's program: for instance, this can be done by calling «fflush(stdout)» or «cout.flush()» in C++, «System.out.flush()» in Java, «Console.Out.Flush()» in C#, «flush(output)» in Pascal, «sys.stdout.flush()» in Python.

Emply lines in the sample are given only for convenience, to make it clear in which order the messages are written. When solving the problem you must not output empty lines and jury's program won't output empty lines too.