配点 : $400$ 点

問題文

縦 $H$ 行横 $W$ 列に区切られたマス目があり、上から $i$ 番目、左から $j$ 列目のマスをマス $(i, j)$ と呼びます。

マス $(i, j)$ には $a_{ij}$ 枚のコインが置かれています。

あなたは以下の操作を何度でも行うことができます。

操作: まだ選んだことのないマスのうち $1$ 枚以上のコインが置かれているマスを $1$ つ選び、そのマスに置かれているコインのうち $1$ 枚を上下左右に隣接するいずれかのマスに移動する

偶数枚のコインが置かれたマスの数を最大化してください。

制約

• 入力はすべて整数である
• $1 \leq H, W \leq 500$
• $0 \leq a_{ij} \leq 9$

入力

入力は以下の形式で標準入力から与えられる。

$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