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.