AT_abc109_d.[ABC109D] Make Them Even

有一个被分成 $H$ 行 $W$ 列的网格，从上往下第 $i$ 行，从左往右第 $j$ 列的格子称为格子 $(i, j)$。

在格子 $(i, j)$ 上放有 $a_{ij}$ 枚硬币。

你可以进行如下操作任意次：

操作：从尚未被选中过且至少有 $1$ 枚硬币的格子中选择一个，将其中 $1$ 枚硬币移动到其上下左右相邻的某一个格子中。

请最大化网格中放有偶数枚硬币的格子的数量。

输入以如下格式从标准输入读入。

$H$ $W$
$a_{11}$ $a_{12}$ ... $a_{1W}$
$a_{21}$ $a_{22}$ ... $a_{2W}$
$\vdots$
$a_{H1}$ $a_{H2}$ ... $a_{HW}$

请输出一组操作序列，使得放有偶数枚硬币的格子的数量最大，格式如下：

$N$
$y_1$ $x_1$ $y_1'$ $x_1'$
$y_2$ $x_2$ $y_2'$ $x_2'$
$\vdots$
$y_N$ $x_N$ $y_N'$ $x_N'$

其中，第一行为操作次数 $N$，满足 $0 \leq N \leq H \times W$。

第 $i+1$ 行（$1 \leq i \leq N$）为第 $i$ 次操作，$y_i, x_i, y_i', x_i'$（$1 \leq y_i, y_i' \leq H$ 且 $1 \leq x_i, x_i' \leq W$），表示将格子 $(y_i, x_i)$ 中的 $1$ 枚硬币移动到其相邻的格子 $(y_i', x_i')$。

如果输出了题目未允许的操作，或输出格式不正确，将被判为 Wrong Answer。

限制

• 所有输入均为整数。
• $1 \leq H, W \leq 500$
• $0 \leq a_{ij} \leq 9$

样例解释 1

按如下方式操作，可以使所有格子的硬币数都变为偶数：

• 将格子 $(2, 2)$ 的 $1$ 枚硬币移动到格子 $(2, 3)$
• 将格子 $(1, 1)$ 的 $1$ 枚硬币移动到格子 $(1, 2)$
• 将格子 $(1, 3)$ 的 $1$ 枚硬币移动到格子 $(1, 2)$

由 ChatGPT 4.1 翻译