Problem L. LCA queries ≡

Statement

This is an interactive problem. You will interact with a server by sending and receiving particular messages.

You are given a complete binary tree of height N having maximum possible number of nodes.

Nodes are numbered from 1 to 2^N − 1.

Your task is to determine the number of root. You can perform requests to find least common ancestor (LCA) of any two nodes to achieve this. You are allowed to perform no more than N requests.

Input format

The first line contains one integer N — height of the tree.

Interaction protocol

To make a request print a line "? X Y", where X and Y — are integer numbers of nodes. After such a request you receive one integer — the number of least common ancestor of these two nodes.

When your program determines the root of the given tree, it should print "! X" and immediately stop.

If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Constraints

1 ≤ N ≤ 10

1 ≤ X, Y < 2^N

Explanation of the samples

The first sample contains the next tree:

Sample tests

3

2

5

7

? 3 6

? 1 5

? 2 4

! 7

1

! 1