Introduction

The problem this one is based on is https://yukicoder.me/problems/no/2496, but not knowing the solution to the original problem has no effect on solving this problem.

Problem Statement

This is an interactive problem.

You are given a positive integer $N$. In addition, permutations $A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N)$ of $(1,2,\dots,N)$ are hidden. You can ask the following question up to $3N$ times.

• Question: Choose integers $i,j$ between $1$ and $N$, inclusive, and ask for the value of $\gcd(A_i,B_j)$.

Constraints

• $1\leq N\leq 1000$
• All inputs are integers.

Input and Output

First, the length $N$ of the permutations is given from standard input.

$N$

Next, repeat asking questions until you can determine $A,B$. Print each question to standard output in the following format.

? $i$ $j$

The answer to the question is given from standard input in the following format.

$X$

Here, $X=\gcd(A_i,B_j)$.

Once you have determined $A,B$, print them to standard output in the following format (print them on a single line). Then, terminate your program immediately.

! $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$

Notes

• After each output, add a newline at the end and flush standard output. Otherwise, you may get TLE.
• If you ask more than $3N$ questions or produce invalid output, the judge result is undefined.
• Terminate your program immediately after printing your answer. Otherwise, the judge result is undefined.
• The judge for this problem is adaptive: it may change $A,B$ as long as this does not contradict the constraints and your previous outputs.

Sample