Monk and BST
Tag(s):

Data Structures, Easy-Medium, Trees

Problem
Editorial
Analytics

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:

1. The left sub-tree contains only nodes with values less than or equal to the parent node; the right sub-tree contains only nodes with values greater than the parent node.
2. If a node has level i, then the subtree rooted at that node should have exactly $2^{L-i}$ number of distinct values in the subtree. Note that it is the number of distinct values in the subtree and not the number of nodes in the subtree.
3. If a is the smallest value in the tree and b is the largest value, then all values from a to b must come atleast once in the tree.

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}$

SAMPLE INPUT
3 16
5
0 3
0 4
1 4
1 7
0 5

SAMPLE OUTPUT
root
r
2
5
rr

Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...