Escape the Tree

All submissions for this problem are available.
### Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/COOK116/mandarin/ESCTRE.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK116/vietnamese/ESCTRE.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK116/bengali/ESCTRE.pdf) as well. Chef is trying to make his birthday party adventurous. He recently heard about *escape the room* games, so he wants to prepare his own version of such a game. First, Chef will lock his friends in the root of a full binary tree with depth $h$, i.e. with $2^{h+1}1$ nodes (numbered $1$ through $2^{h+1}1$). The root has number $1$, but the other nodes may be numbered arbitrarily. His friends can only escape this tree by reaching a *special leaf node*. They do not have any other information about the structure of the tree or the special node. The friends need to find the number of the special node. In order to do that, they may ask at most $2h+1$ queries of the following two types: 1. Choose a node $x$. Chef's response to this query is the distance between node $x$ and the special node. 2. Choose a node $x$ and an integer $y$. Consider all leaf nodes at the distance $y$ from node $x$. If there is at least one such node, Chef chooses one such node and his response is the number of the node he chose. Otherwise, Chef's response is $0$. Help Chef's friends find the special node and escape the tree. ### Interaction  First, you should read a line containing a single integer $T$ denoting the number of test cases. The description of interaction for $T$ test cases follows.  For each test case, you should start by reading a line containing a single integer $h$ ― the height of the full binary tree.  Then, you may ask queries.  To ask a query of the first type, you should print a line containing two spaceseparated integers $1$ and $x$ ($1 \le x \le 2^{h+1}1$). Then, you must read a line containing a single integer ― the answer to your query, or $1$ if the query is invalid or if you have asked too many queries.  To ask a query of the second type, you should print a line containing three spaceseparated integers $2$, $x$ and $y$ ($1 \le x \le 2^{h+1}1$, $0 \le y \le 2h$). Then, you must read a line containing a single integer ― the answer to your query, or $1$ if the query is invalid or if you have asked too many queries.  Finally, you should print a line containing two spaceseparated integers $3$ and $x$, where $x$ is the number of the special leaf node. Then, you must read a line containing a single integer: $1$ if your answer was correct, or $1$ if it was incorrect or if you have asked too many queries. If your answer was correct, you should continue solving the remaining test cases. Note that when you receive an answer $1$, you should immediately terminate your program to receive a Wrong Answer verdict; otherwise, you may receive any verdict. For each test case, the grader decides that you have asked too many queries as soon as it detects that you have printed $2h+3$ lines ― printing the answer is included, so this corresponds to asking more than $2h+1$ queries. Don't forget to flush the output after printing each line! ### Constraints  $1 \le T \le 10$  $2 \le h \le 15$ ### Example ``` You Grader 1 2 1 5 3 2 5 2 0 2 5 3 3 1 3 0 3 3 1 ``` ### Note **Example case 1:** This [tree](https://ibb.co/jvvXnnh) is used by Chef. The special leaf node is node $3$.Author:  ezio_26 
Editorial  https://discuss.codechef.com/problems/ESCTRE 
Tags  cook116, easymedium, ezio_26, interactive, tmwilliamlin, trees 
Date Added:  15032020 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 