_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 <= N <= 500$.
You can make queries of type "_? l r_" to ask B21 the product of all elements in the segment $[ l, r ]$ ($1 <= l <= r <= 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.
*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 :/
## Input
Read an integer $N$ - length of the array. $2 <= N <= 500$.
## Interaction
You can make queries of type "_? l r_" to ask B21 the product of all elements in the segment $[ l, r ]$ ($1 <= l <= r <= 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.
[samples]
## Note
*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 :/
**Definitions**
Let $ N \in \mathbb{Z} $ be the length of the secret array $ A = (a_1, a_2, \dots, a_N) $, where each $ a_i $ is a prime number in $ [2, 10^4] $, and $ A $ is sorted: $ a_1 \leq a_2 \leq \dots \leq a_N $.
Let $ M = 10^9 + 9 $.
Let $ Q $ be the set of queries made, each query is a subsegment $ [l, r] $ with cost $ \frac{1}{(r - l + 1)^2} $.
Total cost constraint: $ \sum_{[l,r] \in Q} \frac{1}{(r - l + 1)^2} \leq 0.45 $.
**Constraints**
1. $ 2 \leq N \leq 500 $
2. Each $ a_i $ is prime and $ 2 \leq a_i \leq 10^4 $
3. $ A $ is non-decreasing
4. For any query $ [l, r] $, the response is $ \prod_{i=l}^r a_i \mod M $
5. Total query cost $ \leq 0.45 $ BTC
**Objective**
Recover the exact array $ A $ using queries such that the total cost does not exceed 0.45 BTC, then output $ !\ a_1\ a_2\ \dots\ a_N $.