Mike has gotten so bored of playing Factor Solitaire that he vows to never play it again! Instead, he has developed an interest in a new game which he calls Factor Klondike.

Josh has a permutation of the first $N$ positive integers $p_1,p_2,\dots ,p_N$, which he keeps hidden from Mike. The goal of the game is to guess Josh's permutation by making as few queries as possible. In one query, Mike selects integers $l,r,x$ such that $1\le l\le r\le N$ and $1\le x\le N$, and Josh tells him whether any of the elements $p_l,p_{l+1},p_{l+2},\dots ,p_r$ contain $x$ as a factor.

Can you help Mike to win as efficiently as possible? You can make at most $4\times {10}^5$ queries.

Constraints

$2\le N\le {10}^4$

$p_1,p_2,\dots ,p_N$ is a permutation of the integers $1,2,\dots ,N$.

Scoring

Let $Q$ be the maximum number of queries made by your program in any test case. Your program will receive the following score:

$Q$	Score
$0\le Q\le 1.35\times {10}^5$	$100$
$1.35\times {10}^5<Q\le 1.45\times {10}^5$	$90$
$1.45\times {10}^5<Q\le 1.55\times {10}^5$	$80$
$1.55\times {10}^5<Q\le 1.65\times {10}^5$	$70$
$1.65\times {10}^5<Q\le 1.8\times {10}^5$	$60$
$1.8\times {10}^5<Q\le 2\times {10}^5$	$50$
$2\times {10}^5<Q\le 2.2\times {10}^5$	$40$
$2.2\times {10}^5<Q\le 2.5\times {10}^5$	$30$
$2.5\times {10}^5<Q\le 3\times {10}^5$	$20$
$3\times {10}^5<Q\le 4\times {10}^5$	$10$
$Q>4\times {10}^5$	$0$

If your program fails to guess the permutation in any test case, then you will receive $0$ points.

Interaction

This is an interactive problem. Note that the interactor is not adaptive, and the target permutation $p_1,p_2,\dots ,p_N$ is generated uniformly at random.

At first, you should read in a single integer on a single line, representing the value of $N$.

Then, you will have the opportunity to make up to $4\times {10}^5$ queries. To make a query, output a line in the form ? l r x. Then, you should read in a single integer on a single line. This integer will be $1$ if any of $p_l,p_{l+1},p_{l+2},\dots ,p_r$ contain $x$ as a factor, and $0$ otherwise.

Finally, once you have made all of your queries, you should output a line in the form ! p_1 p_2 ... p_N, where $p$ is the permutation which you believe is Josh's permutation.

If at any point you format your queries incorrectly, or ask more than $4\times {10}^5$ queries, the interactor will respond with $-1$ on a single line. After receiving this feedback, you should terminate your program to receive a Wrong Answer verdict; otherwise, your program will receive an arbitrary verdict.

If you successfully guess the correct sequence, then you will receive an Accepted verdict for that test case. Your final score for the problem will be determined through the aforementioned scoring mechanism. You will be told the number of queries that you used.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

4
>>> ? 1 2 2
1
>>> ? 3 4 2
0
>>> ? 1 3 3
1
>> ! 4 2 3 1

Explanation

Josh's permutation is $4,2,3,1$.

For the first query, both $p_1$ and $p_2$ contain $2$ as a factor, so the answer is $1$.

For the second query, neither $p_3$ nor $p_4$ contain $2$ as a factor, so the answer is $0$.

For the third query, $p_3$ contains $3$ as a factor, so the answer is $1$.

The permutation has been correctly guessed, and the score for this test case would be $100$.