{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eThis is an interactive problem\u003c/span\u003e. You have to use a \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush\u003c/span\u003e operation right after printing each line. For example, in C++ you should use the function \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e, in Java — \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e, in Pascal — \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e and in Python — \u003cspan class\u003d\"tex-font-style-tt\"\u003esys.stdout.flush()\u003c/span\u003e.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eOsman is lost again :(\u003c/p\u003e\u003cp\u003eHe was trying to come up with the best problem of this contest so he didn\u0027t notice that he was entering a maze. Oh, poor Osman! \u003c/p\u003e\u003cp\u003eOsman 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:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/72df06e51eabd5f93897382f71086baf?v\u003d1726251646\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eYour 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\u0027t, but you don\u0027t want to know, do you?). \u003c/p\u003e\u003cp\u003eOnce 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.\u003c/p\u003e\u003cp\u003eHelp Osman exit the maze! Or not, I don\u0027t care. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eUse standard input to read the responses to the queries.\u003c/p\u003e\u003cp\u003eThe first line contains an integer $$$n$$$ ($$$1 \\le n \\le 29$$$)\u0026nbsp;— The depth of the tree.\u003c/p\u003e\u003cp\u003eFollowing lines will contain responses to your queries\u0026nbsp;— 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.\u003c/p\u003e\u003cp\u003eThe 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 \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush\u003c/span\u003e operation.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eTo make the queries your program must use standard output.\u003c/p\u003e\u003cp\u003eYour program must print the queries\u0026nbsp;— 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 \"\u003cspan class\u003d\"tex-font-style-it\"\u003eend of line\u003c/span\u003e\" after each $$$x_i$$$). After printing each line your program must perform operation \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIn 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.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\n1\n\n2\n\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n1\n\n3\n\n2\n\n! 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}