Description

This is an interactive problem.

Nauuo is a girl who loves binary trees.

One day, she created a binary tree consisting of $n$ nodes. The nodes are numbered from $1$ to $n$. The root of the tree is the node $1$.

However, Nauuo can't remember the tree exactly. She only remembers the distance between every two nodes, you can make some queries on the distance to find the whole binary tree.

The distance between two nodes is the number of edges of the shortest path between the two nodes.

You are allowed to make no more than $30000$ queries, and you only have to tell Nauuo the parent of each node except the root.

Interaction

The interaction starts with a line containing one integer $n$ ($2\le n\le 3000$) --- the number of nodes.

After that, you can make queries.

To make a query, print a line "$\texttt{? u v}$" ($1\le u,v\le n$), then $\texttt{flush}$ the output.

After each query, read a single integer $d$ ($0\le d\le n-1$) --- the distance between $u$ and $v$.

When you find the whole binary tree, print a line "$\texttt{! p}$", $\texttt{flush}$ the output and terminate. $p$ is an array containing $n-1$ integers, where the $i$-th element of $p$ is the parent of node $i+1$.

The interactor will cost no more than $500ms$ if you make no more than $30000$ queries.

Your solution will get $\texttt{Wrong Answer}$ or $\texttt{Time Limit Exceeded}$ if you make more than $30000$ queries.

Your solution will get $\texttt{Idleness Limit Exceeded}$ if you don't print anything or forget to flush the output.

To $\texttt{flush}$ you need to do the following right after printing a query and a line end:

• $\texttt{fflush(stdout)}$ or $\texttt{cout.flush()}$ in C++;
• $\texttt{System.out.flush()}$ in Java;
• $\texttt{flush(output)}$ in Pascal;
• $\texttt{stdout.flush()}$ in Python;
• see documentation for other languages.

Hacks

The first line contains a single integer $n$ ($2\le n\le 3000$) --- the number of nodes.

The second line contains an array $p$ containing $n-1$ integers, where the $i$-th element of $p$ is the parent of node $i+1$.

For hacks, you have to guarantee that the given parents can form a tree.

Example 1

4
1
2
3

? 1 2
? 1 3
? 3 4
! 1 2 1

The binary tree is as follows.

In the first query, the distance between $1$ and $2$ is $1$ ($1\rightarrow2$).

In the second query, the distance between $1$ and $3$ is $2$ ($1\rightarrow2\rightarrow3$).

In the third query, the distance between $3$ and $4$ is $3$ ($3\rightarrow2\rightarrow1\rightarrow4$).

5
4
1

? 4 3
? 2 4
! 1 5 2 1

The binary tree is as follows.