{"raw_statement":[{"iden":"statement","content":"_*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()._\n\nOsman is lost again :(\n\nHe 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! \n\nOsman 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:\n\nYour 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?). \n\nOnce 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.\n\nHelp Osman exit the maze! Or not, I don't care. \n\nUse standard input to read the responses to the queries.\n\nThe first line contains an integer $n$ ($1 <= n <= 29$) — The depth of the tree.\n\nFollowing 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.\n\nThe 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.\n\nTo make the queries your program must use standard output.\n\nYour 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_.\n\nIn 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.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of cities.  \nFor each $ i \\in \\{1, \\dots, N\\} $:  \n- $ (x_i, y_i) \\in \\mathbb{R}^2 $ is the 2D coordinate of city $ i $.  \n- $ p_i \\in \\mathbb{Z} $ is the population (in thousands) of Zoom users in city $ i $.  \n\n**Constraints**  \n1. $ 1 \\leq N < 1000 $  \n2. $ -1000 \\leq x_i, y_i \\leq 1000 $  \n3. $ 1 \\leq p_i < 1000 $  \n\n**Objective**  \nCompute the weighted average location $ (x_a, y_a) $, where weights are user populations:  \n$$\nx_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}\n$$","simple_statement":"Find the weighted average location of Zoom users given cities with coordinates and populations.","has_page_source":false}