C. Divisor Lattice
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Interaction

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:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.

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.

Examples
Input
4

1
Output
? 2 4

! 2 2 4
Input
1
Output
! 0
Note

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.