춤추는 원반

루카는 하노이의 탑 퍼즐을 완전히 익혔고, 원반과 막대를 쓰는 비슷한 게임을 직접 만들었다. 이 퍼즐에는 크기가 서로 다른 나무 원반이 $n$개 있고, 막대는 36개 있다. 원반에는 작은 것부터 순서대로 1부터 $n$까지 번호가 붙어 있다. 막대는 위에서 아래로 1번부터 6번까지 6개의 행, 왼쪽에서 오른쪽으로 1번부터 6번까지 6개의 열에 배치되어 있다.

처음에는 $n$개의 원반이 모두 왼쪽 위 막대에 임의의 순서로 쌓여 있다. 한 단계에서 플레이어는 한 막대 $R$의 맨 위에서 원반 한 개 이상으로 이루어진 묶음을 집어, 순서를 바꾸지 않고 $R$ 바로 아래 또는 바로 오른쪽 막대의 맨 위로 옮길 수 있다. 목표는 모든 원반을 오른쪽 아래 막대에 올려, 위에서 아래로 크기가 커지는 순서로 정렬하는 것이다.

왼쪽 위 막대에 있는 원반의 초기 순서가 주어졌을 때, 퍼즐을 푸는 유효한 단계의 순서를 하나 찾으시오. 해가 항상 존재한다고 가정해도 된다.

첫 줄에 원반의 개수 $n$이 주어진다($1 \le n \le 40\,000$). 다음 줄에는 서로 다른 정수 $d_1, d_2, \ldots, d_n$($1 \le d_k \le n$)이 주어진다. 왼쪽 위 막대에 있는 원반의 초기 순서이며, 아래에서 위 방향이다.

단계의 수를 $m$이라 할 때, $m$개의 줄을 출력하시오. $k$번째 줄에는 네 개의 값 $r_k$, $c_k$, $p_k$, $n_k$를 출력한다.

• $r_k$와 $c_k$는 원반을 집어 올리는 막대의 행과 열이며, 각각 1 이상 6 이하의 정수이다.
• $p_k$는 대문자 "D" 또는 "R"이다. "D"는 원반을 바로 아래 막대로, "R"은 바로 오른쪽 막대로 옮긴다는 뜻이다.
• $n_k$는 이 단계에서 옮기는 원반의 개수인 양의 정수이다.

모든 단계는 위 규칙에 맞아야 하며, 단계들이 퍼즐을 올바르게 풀어야 한다.

예시 그림에서 처음 9단계는 원반을 순서를 바꾸지 않고 모두 6행 5열의 막대로 옮긴다. 이 막대는 오른쪽 아래 목표 막대의 바로 왼쪽에 있다. 다음 단계에서는 맨 위의 원반 5개, 즉 아래에서 위로 (6, 5, 4, 3, 2)인 원반을 목표 막대로 옮긴다. 마지막으로 원반 1을 목표 막대로 옮겨 아래에서 위로 (6, 5, 4, 3, 2, 1)의 순서를 얻는다.