The 0-th and 1-st Frabonacci trees are each single nodes. For all i > 1, the i-th Frabonacci tree is constructed as follows:
The number of vertices in Frabonacci trees grows very quickly, for example there are about 4*10^10 vertices in the 50-th Frabonacci tree.
Create a new node r. This will be the root node of the i-th Frabonacci tree.
Construct the (i-1)-th and (i-2)-th Frabonacci trees.
Attach the (i-2)-th Frabonacci tree as the left subtree of r.
Attach the (i-1)-th Frabonacci tree as the right subtree of r.
To traverse a Frabonacci tree in preorder, perform the following operations:
Let's traverse a Frabonacci tree and enumerate all vertices in the order of their visiting.
There is the 3-rd Frabonacci tree with enumerated vertices on the picture.
Visit the root.
Traverse the left subtree.
Traverse the right subtree.
You are given three ints n, startIndex, finishIndex. Return the shortest route between the vertices startIndex and finishIndex in form of a String in the n-th Frabonacci tree. Each character of the result will be "L", "R" or "U", where "L" means a move to the left son, "R" means the move to the right son, and "U" means the move to