35053번 - 시험지 배부 스페셜 저지

문제

교실에는 가로 $N,ドル 세로 2ドルN,ドル 총 2ドルN^2$개의 책상이 직사각형 격자 형태로 배치되어 있다. 각 책상에는 학생 한 명이 앉아 있다. 선생님인 당신은 가능한 한 빠르게 모든 학생에게 시험지를 나누어 주려 한다.

시험지 배부는 매 초마다 다음과 같이 진행된다.

먼저 시험지를 가지고 있는 학생은 다음 행동을 필요에 따라 수행할 수 있다. 즉, 어떤 학생이 이 행동을 무조건 수행해야 하는 것은 아니다.

• 현재 위치에서 상하좌우로 인접한 책상에 앉은 학생 한 명에게만 시험지를 줄 수 있으며, 이때 주는 시험지의 수는 정확히 $($자신이 가지고 있는 시험지의 수$)-1$장이다.

학생들의 행동이 모두 끝나면, 당신은 아래의 행동을 반드시 수행해야 한다.

• 현재 위치에서 상하좌우로 인접한 책상 중 한 곳으로 이동한다. 그 위치의 학생에게 시험지를 원하는 만큼 주거나, 시험지를 주지 않는다.

당신에게는 시간이 많지 않기 때문에, 최대한 짧은 시간 안에 모든 학생이 시험지를 최소 한 장 이상 가지도록 해야 한다. 이를 만족하는 방법 하나를 찾아주자. 최소 시간에 조건을 만족할 수 있는 방법이라면 어떤 방법이든 정답으로 인정된다. 당신은 어느 책상에서든 배부를 시작할 수 있으며, 처음 배부를 시작할 때도 이동은 반드시 해야 한다.

입력

첫째 줄에 양의 정수 $N$이 주어진다. $(1\le N\le 20)$

출력

첫째 줄에 당신이 시작할 위치 $r_{start}, c_{start}$를 공백으로 구분하여 출력한다. $(1\le r_{start}\le 2N;\ 1\le c_{start}\le N)$

둘째 줄에 모든 학생이 시험지를 최소 한 장 이상 가지게 될 때까지 필요한 최소 시간 $T$를 출력한다. $(1\le T\le 10^9)$

셋째 줄부터 $T$번에 걸쳐 다음을 출력한다:

• 첫째 줄에 시험지를 주는 행동을 할 학생의 수 $S$를 출력한다. $(0\le S\le 2N^2)$
• $S \ge 1$인 경우 둘째 줄부터 $S$개의 줄에 걸쳐, 전달할 학생의 위치 $r_i, c_i$와 그 학생이 시험지를 전달할 방향을 공백으로 구분하여 출력한다. $(1\le r_i\le 2N; 1\le c_i\le N)$ 단, 시험지를 전달하는 $S$명의 학생은 모두 달라야 한다.
• $S+2$번째 줄에 당신이 한 칸 이동할 방향과, 이동한 방향의 학생에게 줄 시험지의 수 $K$를 공백으로 구분하여 출력한다. $(0\le K\le 10^9)$
• 학생이 시험지를 전달할 방향과 당신이 이동할 방향은 L, R, U, D 중 하나의 문자로 출력한다. L은 $(r, c)\rightarrow(r, c-1),ドル R은 $(r, c)\rightarrow(r, c+1),ドル U는 $(r, c)\rightarrow(r-1, c),ドル D는 $(r, c)\rightarrow(r+1, c)$로 이동한다는 뜻이다.

출력해야 하는 모든 수는 정수이다.

제한

노트