2048 is a popular mini-game.

We first introduce the rules of the actual game: 2048 is played on a $4 \times 4$ grid. Each position (cell) can hold at most one tile, and each tile is marked with a number that is a power of 2. In each turn, the player chooses a valid direction (up, down, left, or right; validity will be explained later). The tiles move as far as possible in that direction until they hit a boundary or another tile, while maintaining their relative order. If two tiles that are adjacent and parallel to the chosen direction have the same number, they immediately merge into one tile; the tile that disappears no longer occupies its position. Each tile can merge at most once per turn, and the order of merging is determined by which tile is closer to the chosen direction. A move is valid if and only if it results in at least one tile moving or merging, which implies that after the operation, there must be at least one empty position on the grid. Before the game starts or between turns, the game program randomly generates a tile marked with 2 or 4 in an empty space. The game ends when a tile with 2048 is formed, and the player wins; if the player cannot make a valid move, the game ends, and the player loses.

Now, we want an AI to achieve the highest possible score. Please note that the rules in this problem differ from the actual game. In the actual game, the player does not know the position and value of the randomly generated tiles. In this problem, we provide the random algorithm, and we only generate tiles marked with 2 each time, hoping to achieve a high score based on this.

Game Rules Example

After the state shown in the left figure, the player chooses to move left. The three 4s at the bottom will become one 8 and one 4. Since the two 4s on the left are closer to the direction of movement (left), the 8 should be formed by the leftmost 4 and the second 4 from the left (see the right figure). From the figure, it can be determined that the game program randomly generated a 2 in the bottom-right corner between turns:

Random Algorithm

Given a random seed $seed$ and a constant $MUL = 8221$, a sequence of signed 32-bit random integers $seq$ is generated according to the following rules:

$$seq_0 = seed$$ $$seq_i = (seq_{i-1} * MUL) + (seq_{i-1} \gg 16) \quad (i \ge 1)$$

The $\gg$ symbol denotes a signed right shift. When the result of addition or subtraction is $\ge 2^{31}$ (or $< -2^{31}$), it automatically becomes the negative (or positive) number of equal magnitude in modulo $2^{32}$ arithmetic (Pascal users can use the {$R-} option).

The random numbers required for the 2048 game are integers from $0$ to $15$, representing the tiles numbered from left to right and top to bottom (see the figure below). Each time a random tile needs to be generated, we take numbers from the random sequence one by one and take them modulo 16 until we find a number corresponding to an empty position (not a position already occupied by a tile). The next random number should start from the one following the last selected number. The first random number is $seq_1$.

Typical code for generating the above random sequence in C and Pascal is as follows:

int MUL = 8221;
int seq;

void initSeed(int seed)
{
    seq = seed;
}

int getRand()
{
    return (seq = (seq * MUL) + (seq >> 16)) & 15;
}

Const
    MUL = 8221;
    ArraySize = 1048576;
Var
    Seq: Array[0..ArraySize] of Longint;

Procedure Init(Const Seed: Longint);
Var
    i: Longint;
Begin
    Seq[0] := Seed;
    For i := 1 to ArraySize do
        Seq[i] := (Seq[i - 1] * MUL) + (Seq[i - 1] Shr 16) + Longint(Seq[i - 1] < 0) * $FFFF0000;
End;

Function GetRand(Const i: Longint): Longint;
Begin
    GetRand := Seq[i] and 15;
End;

The output file should contain a sequence of valid operations in order, aiming to obtain tiles with the largest possible marked numbers. The evaluation will be based on the final state after the operations are executed.

The additional file simulate(.exe) can check your output file and simulate it, outputting the final state to the console. Usage: Call simulate [filename: 2048*.out] in the terminal or cmd.exe.

Input

There is no input file for this problem. We specify a set of random seeds here: for the $i$-th test case, use the value $i$ as the random seed ($i = 1, 2, \dots, 20$), corresponding to output files 20481.out through 204820.out.

Output

In the output files 20481.out through 204820.out, the first line should output the random seed corresponding to the problem (note: do not swap the file name and seed order). The second line should list the operations in order (use uppercase letters U, D, L, R for up, down, left, and right, respectively).

Examples

Input 1

(None)

Output 1

1
LLLLLDLLLRDULRRDRUUDRLURLURLLUDLLURLRLLULLLLL

Note

The above example is a valid output for 20481.out. It may not necessarily achieve the full score for this test case.

Subtasks

Each test case is scored individually, and each test case has equal weight. If your output is invalid or does not meet the requirements, the score is 0; otherwise, you receive full marks for that test case. The requirements are as follows:

• For test cases 1-2: Your final state must contain a tile marked with at least 4096.
• For test cases 3-5: Your final state must contain a tile marked with at least 8192.
• For test cases 6-10: Your final state must contain a tile marked with at least 16384.
• For test cases 11-20: Your final state must contain a tile marked with at least 32768.