Łamigłówka – Row and Column Painting Puzzle

This problem is inspired by an advertisement from a mobile game. In this game, you are given an n×m grid, initially uncolored. A target pattern is provided, where each cell is colored with one of the uppercase English letters. In one move, you may choose an entire row or an entire column and repaint all its cells with any color of your choice. (Note that unlike some games where over‐painting causes colors to mix, here repainting simply overwrites the previous color.)

Formally, suppose the target pattern is given by \(P\) where \(P_{i,j}\) is the color of the cell in row \(i\) and column \(j\) (1-indexed). In one operation you choose one row or column and a letter \(L\) (an uppercase English letter) and paint all cells in that row or column with \(L\). The final board is determined in the following way: if a cell is painted more than once, the color from the later operation (in the order you output) will be the final color. You may assume that there is always a solution obtainable in at most \(n+m\) moves.

Your task is to output a valid sequence of operations which, when applied to an initially blank grid, produces the given target pattern. Each operation is of the form:

[ \texttt{ } ]

where Type is either R (if you choose a row) or C (if you choose a column), Index is the 1-indexed number of the row or column being painted, and Color is the uppercase letter you are painting with.

Input and output formats are described below.

inputFormat

The first line contains two integers \(n\) and \(m\) (1 ≤ \(n, m\) ≤ 500) separated by a space, representing the number of rows and columns respectively.

Then follow \(n\) lines, each containing a string of length \(m\) consisting only of uppercase English letters. The \(j\)-th character of the \(i\)-th line is \(P_{i,j}\), the target color of the cell in row \(i\) and column \(j\).

outputFormat

On the first line, output an integer \(k\) (0 ≤ \(k\) ≤ \(n+m\)) representing the number of operations in your sequence.

Then output \(k\) lines, each describing an operation in the following format:

An operation of the form R i L means that you repaint row \(i\) with color \(L\), and an operation of the form C j L means that you repaint column \(j\) with color \(L\).

If there exist multiple valid answers, any one is accepted.

sample

1 1
A

1
R 1 A

</p>