There is a hidden positive integer $$$k$$$ that has exactly $$$n$$$ divisors. These divisors were put into an array $$$a$$$ which was then shuffled into a hidden order.
You can ask the interactor questions of the form ? i j, and you will receive the position of $$$\gcd(a_i, a_j)$$$ in $$$a$$$. Note that since $$$a$$$ contains all divisors of $$$k$$$, this value is guaranteed to exist and be unique.
Using at most $$$3n$$$ queries, determine which indices of $$$a$$$ contain prime numbers.
The input consists of one line containing an integer $$$n$$$ ($$$1\leq n\leq 10^4$$$) — the number of divisors of $$$k$$$.
Note that we make no guarantees about the magnitude of $$$k$$$.
After reading in $$$n$$$, you can make up to $$$3n$$$ queries.
For each query, print a line of the form ? i j ($$$1 \le i, j \le n$$$).
After printing the query, you can then read in an integer $$$x$$$, where $$$a_x = \gcd(a_i, a_j)$$$.
Once you have determined which indices contain prime numbers, print a single line ! m p_1 p_2 ... p_m ($$$0 \le m \le n$$$, $$$1 \le p_i \le n$$$, where $$$m$$$ is the number of prime factors and $$$p_1$$$ through $$$p_m$$$ are their positions in $$$a$$$. This is not counted towards your total of $$$3n$$$ queries.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
The interactor is non-adaptive. This means that the array $$$a$$$ is fixed at the start of the interaction, and does not change after the queries.
4 1
? 2 4 ! 2 2 4
1
! 0
In the first test, after the first query, we know that $$$\gcd(a_2, a_4) = a_1$$$. It can be shown that since $$$n=4$$$, this query result implies that $$$a_2$$$ and $$$a_4$$$ are the prime factors of $$$k$$$.
In the second test $$$n=1$$$, and therefore $$$k=1$$$, because $$$1$$$ is the only positive integer with only one divisor. Since $$$1$$$ has no prime factors, we can simply output ! 0 without making any queries.
