SOLVE
LATER
Monk as always has brought a new task for Fredo. He asks Fredo to create a Binary Search Tree (BST) with $$L$$ levels and $$2^L-1$$ nodes. Let the sum of all node values in the BST be $$M$$. He further adds that $$M$$ should be smallest possible integer greater than $$S$$, where $$S$$ is an integer given by Monk. He states the rules of creating BST as follows:
Level of root is 1, next level is 2 and so on.
Now, he will ask two type of queries to Fredo.
Type $$0$$: Find the closest node to root whose value is equal to $$val$$ and print path to that node from the root. If root has value equal to $$val$$, print "$$root$$". Else print "$$l$$" when we visit left child of any node and "$$r$$" when we visit right child of any node.
Type $$1$$: Tell the value of $$k^{th}$$ node in the tree. The nodes are numbered as:
Here 1,2 and so on are node numbers and A,B etc. are values of nodes.
Finally, he will ask Fredo $$Q$$ queries, each query belonging to one of the types mentioned above. Since, Fredo is new to this concept, help him complete this task.
Input Format:
First line consists of two integers $$L$$ and $$S$$ as described in the question.
Second line consists of $$Q$$, denoting the number of queries.
Each of the following $$Q$$ lines consists of two integers. The first integer denoting the $$type$$ of query and second denoting either $$val$$ or $$k$$ as described in the queries.
Output Format:
For each query, print the required answer in a separate line.
Input Constraints:
$$1 \le L \le 30$$
$$1 \le S \le 10^{18}$$
$$1 \le Q \le 10^5$$
$$0 \le type \le 1$$
$$1 \le k \le 2^L-1$$
$$val$$ is in between minimum and maximum value in tree(inclusive).
Values of $$S$$, $$val$$ and $$k$$ are such that answer would always exist for them.
Node values will be non-negative for all inputs.
$$M$$ will never exceed $$2 \times 10^{18}$$
The tree would look like:
Sum = 3+2+4+2+3+4+5=23 which is smallest possible sum which we can get which is greater than 16.
Query 1: Node with value 3 which is closest to root is root itself.
Query 2: Node with value 4 which is closest to root is right child of root. So, we print "r".
Query 3: Value of node at number 4 is 2.
Query 4: Value of node at number 7 is 5.
Query 5: Node with value 5 which is closest to root is grandchild of root. So, we print "rr" which is path to node from root.