어라, 또 어제로군요

2018년, 2019년, 2020년에 난징항공우주대학교(NUAA)가 국제대학생프로그래밍경시대회(ICPC) 난징 지역 대회를 주최했다. 2021년에는 네 번째로 대회를 연다.

2018년과 2019년 우승은 칭화대학교 팀 Power of Two와 Three Hold Two가 차지했다. 2020년에는 베이징대학교 팀 Inverted Cross가 우승했다. 2021년에는 직전 우승 팀을 포함해 약 $700$개 팀이 참가한다. 올해 우승은 누가 차지할까.

이번에는 전염병 때문에 난징에 모일 수 없지만, 대회를 준비한 모든 스태프와 자원봉사자에게 감사한다.

2018년 대회 K번 문제 Kangaroo Puzzle에서는 다음 게임의 조작 순서를 만들어야 했다.

퍼즐은 $n$행 $m$열 격자이며($1 \le n, m \le 20$), 캥거루가 적어도 $2$마리 있다. 플레이어의 목표는 캥거루들을 조종해 한곳에 모이게 하는 것이다. 일부 칸에는 벽이 있어 캥거루가 들어갈 수 없다. 나머지 칸은 빈칸이다. 캥거루는 상하좌우로 인접한 빈칸으로 이동할 수 있다.

처음에는 모든 빈칸에 캥거루가 한 마리씩 있다. 플레이어는 키보드의 U, D, L, R 버튼을 눌러 캥거루를 조종한다. 캥거루들은 누른 버튼에 따라 동시에 움직인다.

목표를 달성하려면 U, D, L, R로만 이루어진 조작 순서를 최대 $5 \times 10^4$ 단계까지 만들어야 한다.

2020년 대회 A번 문제 Ah, It's Yesterday Once More에서는 위 문제의 다음 코드를 깨뜨리는 입력 격자를 만들어야 했다.

#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;
}

2021년 대회에서는 Paimon이 이 문제의 다른 버전을 준비했다. 주어지는 격자는 $n$행 $n$열이다($2 \leq n \leq 500$). 모든 칸이 빈칸이고, 각 칸에 캥거루가 한 마리씩 있다.

U, D, L, R 버튼으로 캥거루를 조종한다. 캥거루들은 누른 버튼에 따라 동시에 움직인다. 행 $i$, 열 $j$의 칸을 $(i,j)$라고 할 때, 각 캥거루는 다음과 같이 움직인다.

1. U 버튼: $i>1$이면 $(i-1,j)$로 이동한다. 그렇지 않으면 제자리에 머문다.
2. D 버튼: $i<n$이면 $(i+1,j)$로 이동한다. 그렇지 않으면 제자리에 머문다.
3. L 버튼: $j>1$이면 $(i,j-1)$로 이동한다. 그렇지 않으면 제자리에 머문다.
4. R 버튼: $j<n$이면 $(i,j+1)$로 이동한다. 그렇지 않으면 제자리에 머문다.

U, D, L, R 문자로만 이루어진 조작 순서를 만들어야 한다. 이 순서를 적용한 뒤 모든 캥거루가 칸 $(a,b)$에 모여 있어야 한다. 조작 순서의 길이는 $3(n-1)$을 넘을 수 없다.

테스트 케이스는 파일마다 하나뿐이다.

첫 줄에 세 정수 $n$, $a$, $b$($2 \leq n \leq 500$, $1 \leq a,b \leq n$)가 주어진다. $n$은 격자의 크기이고, $(a,b)$는 목표 칸이다.

U, D, L, R 문자로만 이루어진 문자열을 한 줄에 출력한다. 길이는 $3(n-1)$을 넘을 수 없다. 이런 답이 항상 존재함은 증명되어 있다.