使它们都变为偶数

题目描述

有一个被分割成纵 $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}$
$:$
$a_{H1}$ $a_{H2}$ $...$ $a_{HW}$

输出格式

按以下格式输出使放置偶数枚硬币的格子数量最大的操作序列:

$N$
$y_1$ $x_1$ $y_1'$ $x_1'$
$y_2$ $x_2$ $y_2'$ $x_2'$
$:$
$y_N$ $x_N$ $y_N'$ $x_N'$

即,第 $1$ 行输出表示操作次数的、不小于 $0$ 且不超过 $H \times W$ 的整数 $N$。

第 $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。

样例

2 3
1 2 3
0 1 1

3
2 2 2 3
1 1 1 2
1 3 1 2

按如下方式操作,即可使所有格子上的硬币数量都变为偶数:

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

3 2
1 0
2 1
1 0

3
1 1 1 2
1 2 2 2
3 1 3 2

1 5
9 9 9 9 9

2
1 1 1 2
1 3 1 4

数据范围

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

提示

答案不唯一,输出任意合法解即可。