406153: GYM102279 K Kostly Cueries

This is an interactive problem.

Lowie went to a Science fair. His favorite section in the fair is the "interaction" zone, where people spend money to play games and win prizes in different booths.

Lowie went to the Prime booth, where he can win sorted prime array. The boothkeeper B21 kept a prime array secret from Lowie, and he have to guess the whole array by buying queries from B21.

For each queries, Lowie can ask for a subsegment (i.e.: a series of consecutive elements) $$$[l, r]$$$ in the array, B21 will return him with the product of all elements in the subsegment, modulo $$$10^9+9$$$. A query for a subsegment $$$[l, r]$$$ will cost Lowie exactly $$$\frac{1}{(r-l+1)^2}$$$ BTC.

Lowie only have $$$0.45$$$ BTC, help him win the Prime array. Please notice that the array is sorted, and you can ask as many queries as you want, as long as the total cost doesn't exceed the amount that Lowie has.

Oh, and the boothkeeper B21 doesn't like big numbers, so his array will consists only primes in the range of $$$[1, 10^4]$$$.

Read an integer $$$N$$$ - length of the array. $$$2 \le N \le 500$$$.

You can make queries of type "? l r" to ask B21 the product of all elements in the segment $$$[l, r]$$$ ($$$1 \le l \le r \le N$$$) modulo $$$10^9+9$$$.

After the query read its result as an integer. If you read $$$-1$$$, that means your query is not correct, or you have exceeded the total amount of money that you have. Exit the program immediately to get the verdict "Wrong answer". If you don't, you might get an arbitrary verdicts.

When you find out the array, print "$$$!$$$" followed by a space. Then, print $$$N$$$ integers, separated by spaces. This is not counted as a query and will have the cost of $$$0$$$, but you only have one guess. If you failed to get the answer right, your verdict will be "Wrong answer".

After printing any query do not forget to output 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.

5

14322

341

? 1 5

? 4 5

! 2 3 7 11 31

Example 1:

Ask for query: $$$[1, 5]$$$, get the answer of $$$14322$$$.

Ask for query: $$$[4, 5]$$$, get the answer of $$$341$$$.

Somehow got the answer right :/