This problem is a harder version of Permutations & Products. In this version, you can only ask questions where $|i-j|$ is prime.

Larry the magical panda is bored of eating bamboo cookies, so he challenges you to a game. He has a permutation of $1,2,\dots ,N$ which he calls $A$, and you have to guess the permutation by asking questions. The questions work as follows:

• You will give Larry two distinct indices $i$ and $j$ $(1\le i,j\le N,i\ne j)$ such that $|i-j|$ is prime
• Larry will respond with the result of $A_i\times A_j$

Larry allows you to ask at most $N-1$ questions. Can you guess the permutation and win the game?

Constraints

$4\le N\le {10}^5$

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 questions. Each question should be formatted as ? i j followed by a \n character, with $1\le i,j\le N$, $i\ne j$, and $|i-j|$ is prime. In response, you will be given $A_i\times A_j$ on its own line.

If you believe you have the solution, you may output ! followed by a space-separated list of $N$ integers $A_1,A_2,\dots ,A_N$, the permutation $A$. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of $N-1$ questions.

If at any point you attempt an invalid question (such as an invalid output format or a prohibited pair of indices), or you exceed the limit of $N-1$ questions, the interactor 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().

Sample Interaction

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

5
>>> ? 3 5
10
>>> ? 1 4
4
>>> ? 4 2
3
>>> ! 4 3 2 1 5