Reconstructing the Knight's Path

A knight from planet (X) has infiltrated a mysterious castle whose floor is formed by an (n \times n) grid of square stones. By custom, the knight must travel from the northwest corner to the southeast corner moving only horizontally or vertically (no diagonal moves or jumping) and visiting each cell at most once.

During his journey, every time he enters a new cell (the starting cell is not counted), he fires two arrows: one directly to the north and one directly to the west. Along the north wall there are (n) targets (one above each column) and along the west wall there are also (n) targets (one beside each row). When the knight steps into a cell with column (j) (0-indexed), an arrow is shot that increases the count on the north target corresponding to column (j); similarly, when he steps into a cell in row (i), an arrow is shot to the west target corresponding to row (i).

Thus, if we denote the number of arrows on the north targets by (N_0, N_1, \dots, N_{n-1}) and on the west targets by (W_0, W_1, \dots, W_{n-1}), then for a valid path the following holds: [ \begin{aligned} \text{For column }0:&\quad N_0 = #\text{ of down moves made while in column }0, \ \text{For column }j ; (1\le j\le n-1):&\quad N_j = 1 + #\text{ of down moves made while in column }j, \end{aligned} ] [ \text{For row }0:&\quad W_0 = #\text{ of right moves made while in row }0, \ \text{For row }i ; (1\le i\le n-1):&\quad W_i = 1 + #\text{ of right moves made while in row }i. ] It can be shown that if the input counts satisfy (\sum_{j=0}^{n-1} N_j = \sum_{i=0}^{n-1} W_i = 2(n-1)) then there is a unique path from the northwest to the southeast corner.

Your task is to reconstruct the knight's path as a string of moves. Represent a right move by the character 'R' and a down move by the character 'D'. The knight starts at the top‐left cell (which is not counted) and then each move leads to a new cell where arrows are fired as described.

Example: Consider (n=3) with north target counts: 1 1 2 and west target counts: 0 3 1. One valid reconstruction is as follows.

• In column 0: do 1 down move (since \(N_0=1\)).
• Take a right move to enter column 1.
• In column 1: do \(N_1-1 = 0\) down moves.
• Take a right move to enter column 2.
• In column 2: do \(N_2-1 = 1\) down move.

This yields the path: DRRD (moves: D, R, R, D).

Note that the provided test data guarantees that the path is unique.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 1000\)), the size of the grid.

The second line contains \(n\) integers \(N_0, N_1, \dots, N_{n-1}\) (each \(\ge 0\)) representing the number of arrows on the north wall targets (from west to east).

The third line contains \(n\) integers \(W_0, W_1, \dots, W_{n-1}\) (each \(\ge 0\)) representing the number of arrows on the west wall targets (from north to south).

It is guaranteed that \(\sum_{j=0}^{n-1} N_j = \sum_{i=0}^{n-1} W_i = 2(n-1)\) and that there is a unique valid path.

outputFormat

Output a string consisting of exactly \(2(n-1)\) characters, where each character is either 'R' (right move) or 'D' (down move), representing the knight's move sequence from the northwest to the southeast corner.

If \(n = 1\), output an empty string.

sample

3
1 1 2
0 3 1

DRRD