#P1438F. Olha and Igor

    ID: 1092 Type: RemoteJudge 4000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>interactiveprobabilitiestrees*3000

Olha and Igor

No submission language available for this problem.

Description

This is an interactive problem.

Igor wants to find the key to Olha's heart. The problem is, that it's at the root of a binary tree.

There is a perfect binary tree of height hh consisting of n=2h1n = 2^{h} - 1 nodes. The nodes have been assigned distinct labels from 11 to nn. However, Igor only knows hh and does not know which label corresponds to which node.

To find key to Olha's heart he needs to find the label assigned to the root by making queries of the following type at most n+420n+420 times:

  • Select three distinct labels uu, vv and ww (1u,v,wn1 \leq u,v,w \leq n).
  • In response, Olha (the grader) will tell him the label of the lowest common ancestor of nodes labelled uu and vv, if the tree was rooted at the node labelled ww instead.

Help Igor to find the root!

Note: the grader is not adaptive: the labels are fixed before any queries are made.

The first and only line contains a single integer hh (3h183 \le h \le 18) — the height of the tree.

Interaction

You begin the interaction by reading hh.

To make a query for labels u,v,wu, v, w, in a separate line output "? u v w".

Numbers in the query have to satisfy 1u,v,wn1 \le u, v, w \le n. Additionally, uvu \ne v, uwu \ne w, and vwv \ne w.

In response, you will receive 1xn1 \le x \le n, the label of the lowest common ancestor of uu and vv, if the tree was rooted at ww.

In case your query is invalid or you asked more than n+420n+420 queries, program will print 1-1 and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you determine the label assigned to the root, output "! r", where rr is the label of the root.

After printing a 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;
  • see documentation for other languages.

Hack Format

To hack, use the following format.

The first line should contain a single integer hh (height of the binary tree).

On the next line, output a permutation pp of size n=2h1n = 2^h - 1. This represents a binary tree where the root is labelled p1p_1 and for 1<in1 < i \le n, the parent of pip_i is pi2p_{ \lfloor{\frac{i}{2}}\rfloor }.

Input

The first and only line contains a single integer hh (3h183 \le h \le 18) — the height of the tree.

Samples

Sample Input 1

3

2

7

4

Sample Output 1

? 7 3 5

? 1 6 4

? 1 5 4

! 4

Note

The labels corresponding to the tree in the example are [44,77,22,66,11,55,33], meaning the root is labelled 44, and for 1<in1 < i \le n, the parent of pip_i is pi2p_{ \lfloor{\frac{i}{2}}\rfloor }.