Puyo Puyo Stacking

The picture is a play screen of Puyo Puyo. This screen uses a 12 × 6 grid and four puyo colors.

Puyo Puyo is a video game made by Compile Co., Ltd., first released in 1991. The company went bankrupt in 2003, but the Puyo Puyo team moved to Sonic Team and still makes Puyo Puyo today.

Puyo Puyo is a two player game in which each player stacks puyos on a grid. The rules are as follows.

• The game starts with an empty grid.
• A puyo is a round, slime like blob that falls from the top of the screen toward the bottom of the grid.
• Every puyo has a color, and there are $K$ colors.
• Puyos are handled in pairs of two.
• A pair can be moved left and right with the controller, rotated between the horizontal and the vertical orientation, and dropped.
• When a pair is dropped, the two puyos fall one at a time, and each puyo keeps falling until it touches another puyo or the floor of the grid.
• Puyos may be stacked outside the grid, but only above the grid.
• Four or more puyos of the same color connected up, down, left or right form a group, and a group disappears. This is called popping.
• If one dropped pair creates two or more groups at the same time, those groups pop together.
• After a group pops, the remaining puyos fall until they touch the floor or another puyo. If that creates a new group, the new group pops the same way and the rest falls again. This sequence is called a chain.
• No new puyo may be placed before the chain ends.

Sonic Team asked for PPAP (Puyo Puyo Algorithm for Printing). It is not a feature of the game software, it is a program used at special events.

You are given the final state of an $R \times C$ grid. Each cell either holds a puyo of some color or is empty. Drop pairs of puyos one after another so that the board ends in this final state. Every puyo must be inside the grid in the final state. You choose both the colors of the puyos and the place where each pair falls.

The first line contains three integers $R$, $C$ and $K$, separated by spaces.

The next $R$ lines contain the final state you must build. Each line contains $C$ integers separated by spaces, and the first of these lines is the top row of the grid. A number between 1 and $K$ is the color of a puyo, and 0 is an empty cell.

Only inputs whose final state can be built with at most 250 drops are given. The puyos of each column therefore rest on the floor with no gap, and nowhere do four or more puyos of the same color connect.

Print the number of dropped pairs $D$ on the first line.

On each of the next $D$ lines, print four integers that describe how one pair was dropped.

• The first number is 0 if the pair is placed horizontally and 1 if it is placed vertically.
• The second number is the column of the left puyo for a horizontal pair, and the column both puyos fall into for a vertical pair. Columns are numbered from 1 starting at the left.
• The third number is the color of the left puyo or of the upper puyo.
• The fourth number is the color of the right puyo or of the lower puyo.

In a vertical pair the lower puyo falls first and the upper puyo lands on top of it.

Many orders build the same final state, so only the order produced by the following rule is accepted.

Let $h_j$, the height of column $j$, be the number of puyos in column $j$ in the final state, and let $c_i$ be the color of the $i$-th puyo from the bottom of column $j$. Sort the columns by height in increasing order, breaking ties by increasing column number, and fill each column in that order as follows.

• For $i = 1, 3, 5, \dots$, while $i + 1 \le h_j$, print the four integers $1$, $j$, $c_{i+1}$, $c_i$. This drop fills the $i$-th and the $(i+1)$-th cell from the bottom.
• If $h_j$ is odd, one cell at the top is left over. Let $v = 1$ if $c_{h_j}$ is not 1, and $v = 2$ if $c_{h_j}$ is 1. Print the four integers $1$, $j$, $v$, $c_{h_j}$, which fills the top cell and leaves one puyo of color $v$ above it, then print the four integers $1$, $j$, $v$, $v$ twice. Five puyos of color $v$ then connect vertically in this column and pop, so column $j$ is left in its final state. Because $K \ge 3$, the color $v$ always exists.
• For a column with $h_j = 0$, print nothing.

$D$ is the number of lines printed this way.

• $3 \le K \le 6$
• $R = C = 4$ or $R = C = 20$
• $D \le 250$

In the first example the puyos fall as shown below. Each picture has six rows: the bottom four rows are the grid and the top two rows are the space above the grid. Both columns have height 1, so column 2 is filled first because its number is smaller.

0 0 0 0    0 0 0 0    0 0 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 2 0 0    0 2 0 0    0 0 0 0
0 0 0 0 -> 0 0 0 0 -> 0 2 0 0 -> 0 2 0 0 -> 0 0 0 0
0 0 0 0    0 2 0 0    0 2 0 0    0 2 0 0    0 0 0 0
0 0 0 0    0 1 0 0    0 1 0 0    0 1 0 0    0 1 0 0

In the fourth picture five puyos of color 2 connect vertically and pop, and only the puyo of color 1 stays. Column 4 is then filled the same way.

0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 2    0 0 0 2    0 0 0 0
0 0 0 0 -> 0 0 0 0 -> 0 0 0 2 -> 0 0 0 2 -> 0 0 0 0
0 0 0 0    0 0 0 2    0 0 0 2    0 0 0 2    0 0 0 0
0 1 0 0    0 1 0 1    0 1 0 1    0 1 0 1    0 1 0 1