Fiibonacci Tree

Time limit2sMemory limit128 MB

Summary

Given preorder indices of two nodes in a recursively built Fibonacci binary tree, compute the shortest L/R/U path between them without ever materializing the tree.

Level: Medium6 of 10
Topics: Tree, Recursion, Math, Divide and conquer
Solved: No attempts yet

Problem

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.

Create a new node r. This node becomes the root of the ith Fiibonacci tree.
Build the (i-1)th and (i-2)th Fiibonacci trees.
Attach the (i-2)th Fiibonacci tree as the left subtree of r.
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.

Input

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.

Output

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.

Examples4

Example 1
Input
```
3 2 4
```
Expected output
```
URL
```
Example 2
Input
```
3 4 2
```
Expected output
```
UUL
```
Example 3
Input
```
3 5 4
```
Expected output
```
UL
```
Example 4
Input
```
12 10 10
```
Expected output