Dancing Disks

Luka has mastered the Towers of Hanoi puzzle and invented a similar game with disks and rods. The puzzle has $n$ wooden disks of different sizes and 36 rods. The disks are numbered 1 through $n$ in order of increasing size. The rods form 6 rows, numbered 1 through 6 from top to bottom, and 6 columns, numbered 1 through 6 from left to right.

The puzzle starts with all $n$ disks stacked in arbitrary order on the rod in the upper-left corner. In each step, a player can pick up a stack of one or more disks from the top of a single rod $R$ and transfer them, without reordering, to the top of the rod immediately below $R$ or immediately to the right of $R$. The goal is to have all the disks on the rod in the lower-right corner, ordered by increasing size from top to bottom.

Given the initial order of the disks on the upper-left rod, find any valid sequence of steps that solves the puzzle. You may assume that a solution always exists.

The first line contains an integer $n$ ($1 \le n \le 40\,000$), the number of disks. The next line contains $n$ distinct integers $d_1, d_2, \ldots, d_n$ ($1 \le d_k \le n$), the initial order of the disks on the upper-left rod, from bottom to top.

Print $m$ lines, where $m$ is the number of steps in your solution. The $k$-th line contains four values $r_k$, $c_k$, $p_k$, $n_k$.

• $r_k$ and $c_k$ are the row and column of the rod the disks are picked up from, each between 1 and 6.
• $p_k$ is an uppercase letter, "D" or "R", meaning the disks are moved to the rod directly below or directly to the right, respectively.
• $n_k$ is a positive integer, the number of disks moved in this step.

Every step must be valid under the rules above, and the steps must solve the puzzle.

In the example picture, the first 9 steps move all the disks, without reordering, to the rod in row 6, column 5, which is directly left of the target rod in the lower-right corner. The next step moves the top five disks, which are (6, 5, 4, 3, 2) from bottom to top, to the target rod. Finally, disk 1 is moved to the target rod, giving the bottom-to-top order (6, 5, 4, 3, 2, 1).