There is a hidden array $A$ of size $N$, where $A_i$ represents the colour of the $i$th element. You are allowed at most $M$ questions. In each question, you can query a range $[l,r]$ and get the number of distinct colours in that range. Find an array $B$ such that the colour scheme of $B$ is equivalent to the colour scheme of $A$. That is, for any pair $1\le i,j\le N$, either $A[i]=A[j]$ and $B[i]=B[j]$, or $A[i]\ne A[j]$ and $B[i]\ne B[j]$ must hold.

For example, $A=[1,2,3,4,3,3,3,2,2,1]$ and $B=[4,3,2,1,2,2,2,3,3,4]$ have an equivalent colour scheme.

Constraints

$1\le N\le 5000$

$M=120000$

Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

At first, you should read in a line containing the integer $N$.

You will then start the interaction by proceeding with your queries.

Each query should be formatted as ? l r followed by a \n character, with $1\le l\le r\le N$.

In response, the judge will return an integer $x$ on its own line, whose value is the number of distinct integers in the range $[l,r]$ of the hidden array $A$.

If you believe you have the solution, you may output ! followed by a space-separated list of $N$ integers $B_1,B_2,\dots ,B_N$, $1\le B_i\le N$, an array which has an equivalent colour scheme to the hidden array $A$. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the query limit of $M$.

If at any point you attempt an invalid question (such as an invalid output format or an invalid range), or you exceed the query limit $M$, the judge will respond with $-1$. You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Scoring

If you have received a verdict of Accepted, your score for the test case will be calculated as follows, where $K$ is the number of queries that you used.

	Score
$60000<K\le 120000$	$30+\lfloor (120000-K)/2000\rfloor$ points
$50000<K\le 60000$	$60+4\lfloor (60000-K)/1000\rfloor$ points
$K\le 50000$	$100$ points

Your score for a batch is the minimum of the scores of all of the tests in the batch.

Sample Interaction

>>> denotes your output. Do not print this out.

Here, the hidden array $A$ is $[1,2,3]$. One of the possible valid arrays $B$ is $[3,2,1]$.

3
>>> ? 1 2
2
>>> ? 1 3
3
>>> ? 2 3
2
>>> ! 3 2 1