문제

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

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

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

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

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

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

입력

첫째 줄에 양의 정수 이 주어진다.

출력

첫째 줄에 당신이 시작할 위치 를 공백으로 구분하여 출력한다.

둘째 줄에 모든 학생이 시험지를 최소 한 장 이상 가지게 될 때까지 필요한 최소 시간 를 출력한다.

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

• 첫째 줄에 시험지를 주는 행동을 할 학생의 수 를 출력한다.
• 인 경우 둘째 줄부터 개의 줄에 걸쳐, 전달할 학생의 위치 와 그 학생이 시험지를 전달할 방향을 공백으로 구분하여 출력한다. 단, 시험지를 전달하는 명의 학생은 모두 달라야 한다.
• 번째 줄에 당신이 한 칸 이동할 방향과, 이동한 방향의 학생에게 줄 시험지의 수 를 공백으로 구분하여 출력한다.
• 학생이 시험지를 전달할 방향과 당신이 이동할 방향은 L, R, U, D 중 하나의 문자로 출력한다. L은 , R은 , U는 , D는 로 이동한다는 뜻이다.

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

노트

이 예제는 일 때 모든 학생에게 시험지를 배부하는 한 가지 방법을 보여 주며, 이보다 더 작은 를 사용하는 최적해가 존재할 수도 있다. 실제로는 항상 최소한의 를 사용하는 정답을 제출해야 한다.