405056: GYM101755 I Guess the Tree

Jury has a complete binary tree with n = 2^h - 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.

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 p_i, where p_i is the parent of vertex i or 0 if i is the root of the tree. After this your program must terminate.

<interactor's output>

? 1 2

<interactor's output>

? 2 3

<interactor's output>

! 2 0 2

3

<solution's output>

1

<solution's output>

1

<solution's output>

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.