Rubik's Fifteen Puzzle

This problem is a fusion of the Rubik's Cube and the Fifteen puzzle. You are given an \(H \times W\) board where each tile is labeled with a unique integer from \(1\) to \(H \cdot W\). The board is initially in an arbitrary configuration, and your task is to sort the board into the "nice" configuration where the \(i,j\)\-th cell (0-indexed) has the value \(i\times W + j + 1\) (or, equivalently, reading row-wise in 1-indexed order, the board is \(1, 2, \ldots, H \cdot W\)).

The only allowed move is to flip an entire row or an entire column. Flipping a row reverses the order of its elements while flipping a column reverses the order of its elements. Note that these moves are involutions (performing the same flip twice returns the row or column to its original order) and can be applied in any sequence.

Consider the following transformations: Let \(r[i]\) be a flag indicating whether the \(i\)-th row is flipped and \(c[j]\) be a flag indicating whether the \(j\)-th column is flipped. The final board is obtained by first flipping all rows \(i\) for which \(r[i]=1\), and then flipping all columns \(j\) for which \(c[j]=1\). Formally, if we denote the original board by \(A\) and the target board by \(T\) where \(T[i][j]= i\times W + j + 1\), then after performing the flips the final matrix \(B\) satisfies:

[ B[i][j] = A[s][t],]

where

[ s = \begin{cases} H-1-i, & \text{if } c[j]=1, \ i, & \text{if } c[j]=0, \end{cases} \quad \text{and} \quad t = \begin{cases} W-1-j, & \text{if } r[s]=1, \ j, & \text{if } r[s]=0. \end{cases} ]

Your task is to determine a sequence of flips (if one exists) that will transform the board into the target sorted configuration. If there is a valid sequence, output any one sequence of moves. Each move is represented as either "R i" indicating that the \(i\)-th row (1-indexed) is flipped, or "C j" indicating that the \(j\)-th column (1-indexed) is flipped. If there is no solution, output -1.

inputFormat

The first line contains two integers \(H\) and \(W\) \( (1 \leq H,W \leq 10) \) representing the number of rows and columns respectively.

Then follow \(H\) lines, each containing \(W\) integers. The \(j\)-th integer in the \(i\)-th line represents the number on the tile at row \(i\) and column \(j\) of the board.

outputFormat

If a sequence of flips exists that transforms the board into the target sorted configuration, output the number of moves \(K\) on the first line, followed by \(K\) lines each containing a move in the format described above. If no valid sequence exists, output -1.

sample

3 3
1 2 3
4 5 6
7 8 9

0