슬라이딩 퍼즐

퍼즐을 좋아하는 큐빅은 이번에 슬라이딩 퍼즐을 구매했다. 슬라이딩 퍼즐은 $2 \times 2N$ 크기의 격자로 되어 있다. 격자의 행은 위에서부터 $1$번과 $2$번, 열은 왼쪽부터 $1$번부터 $2N$번까지 번호가 매겨져 있다.

처음에 윗줄에는 수열 $[1, 2, \dots, N, 1, 2, \dots, N]$이 놓여 있고 아랫줄의 모든 칸은 비어 있다.

예를 들어 $N=4$일 때의 초기 상태는 다음과 같다.

큐빅은 한 번의 행동으로 숫자가 있는 칸 하나를 선택하고, 그 칸과 상하좌우로 인접한 빈칸으로 숫자를 옮길 수 있다. 숫자가 있던 칸은 빈칸이 된다.

큐빅은 행동을 수행하여 윗줄을 다음 수열로 만들려고 한다. $[1, 1, 2, 2, \dots, N, N]$이어야 하고, 아랫줄의 모든 칸은 다시 비어 있어야 한다.

예를 들어 $N=4$일 때의 목표 상태는 다음과 같다.

큐빅이 목표 상태를 만드는 데 필요한 최소 행동 횟수와 실제 이동 순서를 구해보자.

첫 번째 줄에 수열에 등장하는 서로 다른 정수의 개수를 나타내는 정수 $N$이 주어진다.

첫 번째 줄에 목표 상태를 만드는 데 필요한 최소 행동 횟수 $M$을 출력한다.

그다음 $M$개의 줄에 걸쳐, 각 $i$에 대해 $i$번째 줄에 두 정수 $r_i$, $c_i$와 길이가 1인 문자열 $d_i$를 공백으로 구분하여 출력한다. 이는 현재 상태에서 숫자가 있는 $(r_i, c_i)$칸의 숫자를 $d_i$가 나타내는 방향으로 한 칸 옮기는 행동을 의미한다.

• U: 위쪽 칸으로 옮긴다.
• D: 아래쪽 칸으로 옮긴다.
• L: 왼쪽 칸으로 옮긴다.
• R: 오른쪽 칸으로 옮긴다.

숫자를 옮길 칸은 격자 안에 있어야 하며, 숫자를 옮기기 전에는 비어 있어야 한다.

가능한 최적 이동 순서가 여러 개라면 그중 아무것이나 출력한다.

• $1 \le N \le 500$
• $1 \le i \le M$