I. Guess the Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jury has a complete binary tree with n = 2h - 1 vertices. Its vertices are numbered with distinct integers from 1 to n, but you don't know which vertices are connected with which.

You can ask a jury's program, what is the distance between some two vertices. You must restore tree structure with at most 2.5·h·n such queries.

Interaction

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

In the very beginning your program gets a single integer n (1 ≤ n ≤ 1023, n + 1 is the power of two) — the number of vertices in the tree.

After that you can make at most 2.5·h·n queries. To make a query, output character «?» and two integers from 1 to n — numbers of vertices x and y you want to know the distance between. As a response a single integer will be given to you — the distance between vertices x and y.

Once you find out a complete tree structure, output character «!», and then n integers pi, where pi is the parent of vertex i or 0 if i is the root of the tree. After this your program must terminate.

Example
Input
<interactor's output>

? 1 2

<interactor's output>

? 2 3

<interactor's output>

! 2 0 2
Output
3

<solution's output>

1

<solution's output>

1

<solution's output>
Note

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.