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 positive integers , 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 such that and , and Josh tells him whether any of the elements contain as a factor.

Can you help Mike to win as efficiently as possible? You can make at most queries.

#### Constraints

is a permutation of the integers .

#### Scoring

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

Score | |
---|---|

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

#### Interaction

This is an interactive problem. **Note that the interactor is not adaptive, and the target permutation is generated uniformly at random.**

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

Then, you will have the opportunity to make up to 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 if any of contain as a factor, and 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 is the permutation which you believe is Josh's permutation.

If at any point you format your queries incorrectly, or ask more than queries, the interactor will respond with 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 .

For the first query, both and contain as a factor, so the answer is .

For the second query, neither nor contain as a factor, so the answer is .

For the third query, contains as a factor, so the answer is .

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

## Comments