Problem Background

PA 2024 4C

Problem Description

This problem is translated from PA 2024 Round 4 Puzzle 3

Bytie enjoys playing mobile games. However, he is annoyed by the frequent ads for other games within the game, where the players perform poorly. The purpose of these ads is to frustrate the viewers, thereby increasing their desire to play. Bytie has a particularly strong impression of one such ad (which you might have seen as well).

Drawing inspiration from anything, Bytie decided to create a problem based on the above game. He will select a target pattern of size $n \times m$, and the game will be played on a grid of the same size, initially uncolored. In one operation, he can choose a row or a column and recolor all the squares in that row or column with a color of his choice (note that this is more flexible than the game in the image, where repeating the same color on a cell would mix the colors). To formalize the problem, he labeled all the colors with uppercase English letters. Can you help him write a program that, for each given grid, provides the correct sequence of operations to achieve the target pattern? You can assume that the input guarantees the target pattern can be achieved with at most $n + m$ operations.

Input Format

The first line contains two integers $n$ and $m\ (1 \le n, m \le 2\,000)$, representing the number of rows and columns of the grid, respectively.

The next $n$ lines each contain a string of length $m$. The string consists of uppercase letters, where the $j$-th character of the $i$-th string represents the color of the cell in the $i$-th row and $j$-th column of the target pattern.

It is guaranteed that the given target pattern can be achieved with at most $n + m$ recoloring operations.

Output Format

The first line of the output contains an integer $r\ (1 \le r \le n + m)$, representing the number of operations to be performed. The next $r$ lines describe the operations.

To describe an operation, first output either R or K, indicating whether you want to recolor a row or a column (R for row, K for column). Then, leave a space and output the number of the row or column you wish to recolor, with rows numbered from top to bottom from $1$ to $n$ and columns numbered from left to right from $1$ to $m$. Finally, leave another space and output an uppercase English letter indicating the color you want to recolor that row or column to.

Note that you do not need to minimize the number of operations—just ensure that it does not exceed $n + m$.

Sample Input and Output

Sample Input #1

5 5
AAPAA
APPAA
AAPAA
AAPAA
APPPA

Sample Output #1

10
R 1 Z
K 4 A
K 2 P
R 5 P
R 4 A
R 3 A
R 1 A
K 5 A
K 3 P
K 1 A

Sample Input #2

2 3
AAA
PPP

Sample Output #2

2
R 2 P
R 1 A

Notes

Assume P represents green, A represents yellow, and Z represents blue. The sequence of operations in Sample 1 is illustrated below:

见题面 Input 部分

见题面 Output 部分