Background

PA 2024 4C.

Problem Description

This problem is translated from PA 2024 Round 4 Łamigłówka 3.

Bytie likes playing mobile games. However, what annoys him is that these games often contain ads for other games, and the people playing in those ads do terribly. The purpose of this is to make the viewer feel frustrated, and then want to keep playing. Bytie is especially impressed by one such ad (you may have seen it too).

Since inspiration can come from anything, Bytie decides to create a problem based on the game above. He will choose a target pattern of size $n\times m$. The game is played on an $n\times m$ grid, where initially no cells are colored. In one operation, he can choose one row or one column, and recolor all cells in that row (or column) into a color of his choice (note that this is more flexible than the game in the picture, because in the pictured game, recoloring the same cell would mix colors). To make the problem more formal, he labels all colors with capital English letters. Can you help him write a program that, for each given grid, outputs a correct sequence of operations to obtain the target pattern? You may assume that in the input, the target pattern can be obtained in 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.

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

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

Output Format

The first line should contain an integer $r\ (1\le r\le n+m)$, the number of operations to perform. Then output $r$ lines describing the operations.

To describe one operation, first output R or K, indicating whether you want to recolor a row or a column (R means recolor a row, K means recolor a column). Then output a space, the index of the row or column you want to recolor: rows are numbered from $1$ to $n$ from top to bottom, and columns are numbered from $1$ to $m$ from left to right. Then output another space and an uppercase English letter, the color you want to recolor that row or column into.

Note that you do not need to minimize the number of operations; you only need to use at most $n+m$ operations.

5 5
AAPAA
APPAA
AAPAA
AAPAA
APPPA

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

2 3
AAA
PPP

2
R 2 P
R 1 A

Hint

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

Translated by ChatGPT 5