_*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 <= n <= 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 $2 k$ and $2 k + 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 <= n <= 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 <= x_i <= 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.
## Input
Use standard input to read the responses to the queries.The first line contains an integer $n$ ($1 <= n <= 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.
## Output
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 <= x_i <= 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.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of cities.
For each $ i \in \{1, \dots, N\} $:
- $ (x_i, y_i) \in \mathbb{R}^2 $ is the 2D coordinate of city $ i $.
- $ p_i \in \mathbb{Z} $ is the population (in thousands) of Zoom users in city $ i $.
**Constraints**
1. $ 1 \leq N < 1000 $
2. $ -1000 \leq x_i, y_i \leq 1000 $
3. $ 1 \leq p_i < 1000 $
**Objective**
Compute the weighted average location $ (x_a, y_a) $, where weights are user populations:
$$
x_a = \frac{\sum_{i=1}^{N} p_i x_i}{\sum_{i=1}^{N} p_i}, \quad y_a = \frac{\sum_{i=1}^{N} p_i y_i}{\sum_{i=1}^{N} p_i}
$$