Fiibonacci Tree

The 0th and 1st Fiibonacci trees each consist of a single node. For every i greater than 1, the ith Fiibonacci tree is built as follows.

1. Create a new node r. This node becomes the root of the ith Fiibonacci tree.
2. Build the (i-1)th and (i-2)th Fiibonacci trees.
3. Attach the (i-2)th Fiibonacci tree as the left subtree of r.
4. Attach the (i-1)th Fiibonacci tree as the right subtree of r.

The number of vertices in a Fiibonacci tree grows very quickly. For example, the 50th Fiibonacci tree has more than 4 x 10^10 vertices.

Vertices are numbered in the order they are visited by a preorder traversal of the tree.

Given N, a start position, and a target position, find the shortest path from the start position to the target position in the Nth Fiibonacci tree. The distance between adjacent nodes is 1.

The first line contains N, the start position, and the target position separated by spaces.

N is an integer with 0 <= N <= 50. The start and target positions are positive integers no greater than 1,000,000,000, and each is no greater than the number of vertices in the Nth Fiibonacci tree. The two positions may be the same.

Print the shortest path from the start position to the target position. Use L for moving to a left child, R for moving to a right child, and U for moving to a parent. If the two positions are the same, print nothing.