Insane Drift

Time limit0.5sMemory limit1024 MB

Summary

Given a target (X, Y), decide whether a car that doubles its step length on each repeated R or U can reach it in at most 4000 moves, and output a move sequence if so.

Level: Medium7 of 10
Topics: Math, Greedy, Bit manipulation
Solved: No attempts yet

Problem

An infinitely large two-dimensional coordinate plane has Chaewan in a car at the origin. Chaewan can move the car by choosing one of the two operations below.

R: moves the car in the direction of increasing $x$ coordinate. If R has been chosen $k$ times in a row, the car moves $2^{k-1}$ .
U: moves the car in the direction of increasing $y$ coordinate. If U has been chosen $k$ times in a row, the car moves $2^{k-1}$ .

Chaewan wants to reach the position $(X, Y)$ using at most 4000 operations. Determine whether Chaewan can reach that coordinate, and if so, output any one sequence of operations. The car must be exactly at $(X, Y)$ after all operations are performed for it to count as reached.

Input

The first line contains $X$ and $Y$ , separated by a space. ( $0 \le X, Y \le 10^{18}$ , $(X, Y) \neq (0, 0)$ )

Output

If Chaewan can reach $(X, Y)$ , output a string of length at least 1 and at most 4000 consisting only of the characters R and U. Applying the characters in order must place the car exactly at $(X, Y)$ . If several answers exist, any of them is accepted.

If Chaewan cannot reach the position, output impossible.

Examples2

Example 1
Input
```
8 3
```
Expected output
```
RURRURRUR
```
Example 2
Input
```
0 16
```
Expected output
```
impossible
```