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)~
- 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?
~3 \le N \le 10^5~
Subtask 1 [10%]
~N = 3~
Subtask 2 [90%]
No additional constraints.
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~ and ~i \ne j~. 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
cout << flush (depending on whether you use
cout). In Java, this can be done with
System.out.flush(). In Python, you can use
>>> denotes your output. Do not print this out.
5 >>> ? 4 5 5 >>> ? 2 4 3 >>> ? 2 3 6 >>> ! 4 3 2 1 5