Description

There is a rooted tree with $n$ nodes, rooted at $1$. You need to determine the structure of this tree through several queries.

You can use two types of queries:

1. ? 1 u v With this query, you can get the distance between $u$ and $v$.
2. ? 2 u With this query, you can get the size of the subtree of $u$ and all nodes in the subtree of $u$.

Please determine the structure of the tree while making the interactive library output no more than $40000$ numbers.

Interaction

Input the size of the tree $n$ to start the interaction.

During the interaction, you may make the two types of queries described above.

For the first type of query, the interactive library will return a non-negative integer, which is the distance between node $u$ and node $v$.

For the second type of query, the interactive library will first return a positive integer $num$, which is the size of the subtree of $u$. Then, on the same line, it will return $num$ positive integers, which are all nodes in the subtree of $u$ (the order of the nodes will be shuffled).

After you have determined the answer, output one line in the form ! fa[2] fa[3] ... fa[n] to stop the interaction, where $fa[i]$ denotes the parent of node $i$ in this tree.

After you output a line, please flush the buffer:

• In C++, use fflush(stdout) or cout.flush().
• In Pascal, use flush(output).
• In Python, use stdout.flush().
• For other languages, please check the documentation by yourself.

Input Format

See "Interaction".

Output Format

See "Interaction".

5

1

5 1 5 2 4 3

3 4 2 5

1 3

? 1 1 2

? 2 1

? 2 2

? 2 3

! 1 1 2 2

Hint

For $100\%$ of the testdata: $2 \leq n \leq 5000$, $1 \le u, v \le n$.

Translated by ChatGPT 5