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