Each cell of an grid is either inhabited or uninhabited. The rows are numbered from top to bottom, and the columns are numbered from left to right. A grid point is represented by coordinates , where and .
You must output a path along the grid lines from to . In one move, you may move to a vertically or horizontally adjacent grid point, and you may not leave the grid.
For each inhabited cell, a cost of is incurred if the path visits at least one of the cell's four corners. Even if the path visits multiple corners of the same cell, that cell's cost is counted only once. The cost of a path is the number of cells for which a cost is incurred.
See the Scoring section for the exact scoring rules.
The input is given in the following format.
For each test case, print the following two lines.
must be a string of length , and each character must be one of U, D, L, and R. These characters indicate a move by one grid point upward, downward, leftward, and rightward, respectively.
The movement sequence represented by must start at , remain inside the grid at all times, and end at .
Each subtask is scored independently. The approximation-ratio criteria below apply equally to every subtask.
For each test case, let be the optimal cost and let be the actual cost of the valid path printed by the contestant. Define the approximation ratio as follows.
In the first test case, there are no inhabited cells, so the printed path has cost .
In the second test case, the left cell is inhabited. Since the starting point is one of its corners, every path has cost at least . The sample path has cost .
In the third test case, an inhabited cell exists, but the printed path does not visit any of its corners. Therefore, the path has cost .
Each test case is given in the following format.
Each is a string of length , and every character is either 0 or 1.
For a cell , where and , the cell is inhabited if the -th character of is 1, and uninhabited if it is 0.
must be exactly equal to the actual cost of the printed path. The following condition must also hold.
0 or 1.Let be the maximum value of among all test cases in a subtask. You receive the highest percentage whose condition is satisfied.
Condition | Percentage awarded |
|---|---|
for every test case | |
Otherwise |
In the final condition, , , and refer to values from the same test case. The final score is the sum of the scores obtained from the four subtasks.
If any printed path is invalid, or if a printed cost differs from the actual cost of its path, the submission receives points.
| 3 | 15 | Additional condition: in every test case. |
| 4 | 65 | Additional condition: in every test case. |
In the fourth test case, the optimal cost is , while the printed path has cost . Therefore, the approximation ratio for this test case is
Since the approximation ratio of every test case in the sample input is at most , this sample output satisfies the condition for the highest scoring percentage in every subtask.