On the vast plains of the Serengeti lives a clan of ~n~ lions, each a devoted practitioner of Brazilian Jiu-Jitsu (BJJ). After weeks searching across the golden grass, you have finally found them! Now, you'd like to find the three best fighters of the pride.

You assign each lion a number from ~1~ to ~n~. Each lion also has a secret skill level, an integer from ~1~ to ~n~, and no two lions have the same skill level. The three best fighters are the lions with the three highest skill levels.

You don't know the lions' skill levels, but you can test them. You can choose any two lions to fight, and observe who the winner is. The lion with the higher skill level will always win, and since their skill levels are unique, there will always be a winner.

The sun is setting soon, and the lions are already looking a little sleepy, so you have a limited number of fights to determine who the three best fighters are.

Interaction

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your program and writes to its standard input. The interaction must follow the format below.

The interactor first sends one integer ~n~ ~(3 \leq n \leq 1024)~, the number of lions in the pride.

You may then conduct up to ~1050~ fights to determine the three lions with the highest skill levels. To conduct a fight, print a line in the form ~l_1\ l_2\ \texttt{?}~, where ~1 \leq l_i \leq n~ and ~l_1 \neq l_2~, meaning that lions ~l_1~ and ~l_2~ will fight. The interactor will respond with a single integer ~l_w~, meaning that lion ~l_w~ won the fight.

Once you have determined the three best fighters, print a line in the form ~l_1\ l_2\ l_3\ \texttt{!}~, where ~1 \leq l_i \leq n~, meaning that you believe:

• Lion ~l_1~ has the highest skill level.
• Lion ~l_2~ has the second-highest skill level.
• Lion ~l_3~ has the third-highest skill level.

You will receive a Wrong Answer if:

• You conduct more than ~1050~ fights, or
• You try to make a lion fight itself (~l_1 = l_2~), or
• You try to make a lion fight that is not in the range ~[1, n]~, or
• Your final answer is wrong.

After printing each line, you must flush stdout. Failure to do so may result in an Idleness Limit Exceeded verdict.

For C++, you may use cout << endl to output, or call cout.flush() after each output.

For Python, use flush=True in print(), or call sys.stdout.flush() after each output.

Example

Interaction 1

> 4
< 1 2 ?
> 2
< 3 4 ?
> 3
< 2 3 ?
> 2
< 1 4 ?
> 4
< 2 3 4 !

You conduct the following fights:

• Lion ~1~ fights lion ~2~. Lion ~2~ wins.
• Lion ~3~ fights lion ~4~. Lion ~3~ wins.
• Lion ~2~ fights lion ~3~. Lion ~2~ wins.
• Lion ~1~ fights lion ~4~. Lion ~4~ wins.

From this, you can determine:

• Lion ~2~ has the highest skill level.
• Lion ~3~ has the second-highest skill level.
• Lion ~4~ has the third-highest skill level.
• Lion ~1~ has the lowest skill level (but I'm sure they're great at other stuff!)

Interaction 2

> 3
< 1 2 ?
> 1
< 2 3 ?
> 2
< 1 2 3 !