Under construction

Still being built. Things may change

Oops, It's Yesterday Twice More

Time limit1sMemory limit1024 MB

Summary
Given an n by n grid with one kangaroo per cell, output a U/D/L/R button sequence of length at most 3(n-1) that gathers all kangaroos at cell (a, b).
Level

Medium6 of 10

Topics
Implementation, Simulation, Math
Solved
No attempts yet

Statement

In 2018, 2019, and 2020, Nanjing University of Aeronautics and Astronautics (NUAA) hosted the International Collegiate Programming Contest (ICPC) Nanjing regional. In 2021, NUAA hosts it for the fourth time.

Team Power of Two and team Three Hold Two from Tsinghua University won the championship in 2018 and 2019. In 2020, team Inverted Cross from Peking University won. In 2021, around 700700 teams, including the defending champion, take part in the contest. Who will win this year?

The pandemic prevents us from gathering in Nanjing this time. We thank all staff and volunteers for their hard work on this contest.

In the 2018 contest, problem K, Kangaroo Puzzle, asked contestants to construct an operation sequence for this game:

The puzzle is a grid with nn rows and mm columns (1≤n,m≤201 \le n, m \le 20), and some (at least 22) kangaroos stand in the puzzle. The player's goal is to control them so that they gather together. Some cells have walls, and kangaroos cannot enter those cells. The other cells are empty. Kangaroos can move from an empty cell to an adjacent empty cell in four directions: up, down, left, and right.

At the beginning, there is exactly one kangaroo in every empty cell. The player controls the kangaroos by pressing the buttons U, D, L, R on the keyboard. The kangaroos move simultaneously according to the button pressed.

The contestant must construct an operating sequence of at most 5×1045 \times 10^4 steps, consisting only of U, D, L, R, to achieve the goal.

In the 2020 contest, problem A, Ah, It's Yesterday Once More, asked contestants to construct an input map that hacks the following code for the problem described above:

#include <bits/stdc++.h>
using namespace std;
string s = "UDLR";
int main()
{
  srand(time(NULL));
  for (int i = 1; i ≤ 50000; i++) putchar(s[rand() % 4]);
  return 0;
}

In the 2021 contest, Paimon prepares another version of the problem. You are given a grid with nn rows and nn columns (2≤n≤5002 \leq n \leq 500). All cells are empty, and one kangaroo stands in each cell.

You control the kangaroos with the buttons U, D, L, R. The kangaroos move simultaneously according to the button pressed. For a kangaroo in the cell in row ii and column jj, denoted (i,j)(i,j):

  1. Button U: it moves to (i−1,j)(i-1,j) if i>1i>1. Otherwise, it stays in the same cell.
  2. Button D: it moves to (i+1,j)(i+1,j) if i<ni<n. Otherwise, it stays in the same cell.
  3. Button L: it moves to (i,j−1)(i,j-1) if j>1j>1. Otherwise, it stays in the same cell.
  4. Button R: it moves to (i,j+1)(i,j+1) if j<nj<n. Otherwise, it stays in the same cell.

You must construct an operating sequence consisting only of the characters 'U', 'D', 'L', and 'R'. After applying it, every kangaroo must gather at the cell (a,b)(a,b). The length of the sequence cannot exceed 3(n−1)3(n-1).

Input

There is only one test case in each test file.

The first and only line contains three integers nn, aa, bb (2≤n≤5002 \leq n \leq 500, 1≤a,b≤n1 \leq a,b \leq n), the size of the grid and the target cell.

Output

Output one line containing a string made only of the characters 'U', 'D', 'L', and 'R'. Its length must not exceed 3(n−1)3(n-1). It can be proved that such an answer always exists.

Examples2

  1. Example 1

    Input
    3 3 3
    
    Expected output
    RRDD
    
  2. Example 2

    Input
    4 3 2
    
    Expected output
    DLDLDLUR