407235: GYM102700 E Enter to the best problem of this contest!

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

Osman is lost again :(

He was trying to come up with the best problem of this contest so he didn't notice that he was entering a maze. Oh, poor Osman!

Osman is lost in a really symmetrical maze: The maze looks like a perfect binary tree of depth $$$n$$$ $$$(1\leq n\leq 29)$$$ and, luckily, we have a map of the maze. Each node of the binary tree is named by a number and, for each node $$$k$$$, the two children of this node (if any) are named by $$$2k$$$ and $$$2k + 1$$$. For instance, when the depth of the binary tree is $$$4$$$, then the maze looks like this:

Your task is to find Osman. He is unable to move in one of the nodes of the tree. You have a device where you can make queries, each query is a single integer $$$k$$$ from $$$1$$$ to $$$2^n-1$$$. Flush the output stream after printing each query. The device will provide you with the distance from $$$k$$$ to the node where Osman is. You can do at most $$$29$$$ queries to the device before it explodes (or maybe it doesn't, but you don't want to know, do you?).

Once you find Osman, print "! $$$x$$$" (without quotes), where $$$x$$$ is the node where Osman is, and terminate your program normally immediately after flushing the output stream.

Help Osman exit the maze! Or not, I don't care.

Use standard input to read the responses to the queries.

The first line contains an integer $$$n$$$ ($$$1 \le n \le 29$$$) — The depth of the tree.

Following lines will contain responses to your queries — The distance between the node where Osman is and the node that you sent. The $$$i$$$-th line is the response to your $$$i$$$-th query.

The testing system will allow you to read the response on the query only after your program print the query for the system and perform the flush operation.

To make the queries your program must use standard output.

Your program must print the queries — A query consist of an integer number $$$x_i$$$ ($$$1 \le x_i \le 2^n-1$$$). Print one query per line (do not forget "end of line" after each $$$x_i$$$). After printing each line your program must perform operation flush.

In case your program find the node $$$x$$$ where Osman is, print string "! $$$x$$$" (without quotes), where $$$x$$$ is the answer, and terminate your program. An accepted solution should make at most 29 queries, printing the answer does not count as a query.

2

1

2

0

1

3

2

! 2