AT_arc119_d.[ARC119D] Grid Repainting 3

有一个由 $H$ 行 $W$ 列的格子组成的画布。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$，其中 $1 \leq i \leq H$，$1 \leq j \leq W$。最初，如果 $s_{i, j} = $ R，则该格子被涂成红色；如果 $s_{i, j} = $ B，则被涂成蓝色。

你可以进行任意次以下两种操作中的一种：

操作 X：选择一个红色格子，将该格子所在的整行（包括自身）全部涂成白色。
操作 Y：选择一个红色格子，将该格子所在的整列（包括自身）全部涂成白色。

请给出一种操作顺序，使得最终被涂成白色的格子数最大，并输出一种操作方案。

输入通过标准输入给出，格式如下：

$H$ $W$
$s_{1, 1}$ $s_{1, 2}$ $s_{1, 3}$ $\cdots$ $s_{1, W}$
$s_{2, 1}$ $s_{2, 2}$ $s_{2, 3}$ $\cdots$ $s_{2, W}$
$s_{3, 1}$ $s_{3, 2}$ $s_{3, 3}$ $\cdots$ $s_{3, W}$
$\vdots$
$s_{H, 1}$ $s_{H, 2}$ $s_{H, 3}$ $\cdots$ $s_{H, W}$

请按以下格式输出：

$n$
$t_1$ $r_1$ $c_1$
$t_2$ $r_2$ $c_2$
$t_3$ $r_3$ $c_3$
$\vdots$
$t_n$ $r_n$ $c_n$

其中，$n$ 表示操作次数，$t_i$、$r_i$、$c_i$（$1 \leq i \leq n$）表示第 $i$ 次操作选择了格子 $(r_i, c_i)$ 并执行了操作 $t_i$。$t_i$ 必须为 X 或 Y。

如果有多种方案，输出任意一种均可。

限制条件

• $1 \leq H \leq 2500$
• $1 \leq W \leq 2500$
• $s_{i, j}$ 只可能为 R 或 B（$1 \leq i \leq H,\ 1 \leq j \leq W$）
• $H, W$ 均为整数

样例解释 1

例如，按如下方式操作，可以将 $10$ 个格子涂成白色：

• 首先，选择格子 $(1, 1)$，执行操作 X。
• 然后，选择格子 $(4, 3)$，执行操作 Y。
• 接着，选择格子 $(4, 1)$，执行操作 X。
  无法将超过 $11$ 个格子涂成白色。
  

样例解释 2

可以将所有格子都涂成白色。

样例解释 3

由于没有任何红色格子，无法进行任何操作。

由 ChatGPT 4.1 翻译