問題文
縦 H 行横 W 列に区切られたマス目があり、上から i 番目、左から j 列目のマスをマス (i,j) と呼びます。
マス (i,j) には aij 枚のコインが置かれています。
あなたは以下の操作を何度でも行うことができます。
操作: まだ選んだことのないマスのうち 1 枚以上のコインが置かれているマスを 1 つ選び、そのマスに置かれているコインのうち 1 枚を上下左右に隣接するいずれかのマスに移動する
偶数枚のコインが置かれたマスの数を最大化してください。
制約
- 入力はすべて整数である
- 1leqH,Wleq500
- 0leqaijleq9
入力
入力は以下の形式で標準入力から与えられる。
H W
a11 a12 ... a1W
a21 a22 ... a2W
:
aH1 aH2 ... aHW
出力
偶数枚のコインが置かれたマスの数が最大となるような操作の列を次の形式で出力せよ。
N
y1 x1 y1′ x1′
y2 x2 y2′ x2′
:
yN xN yN′ xN′
すなわち、1 行目には操作の回数を表す 0 以上 HtimesW 以下の整数 N を出力せよ。
i+1 (1leqileqN) 行目には i 回目の操作を表す整数 yi,xi,yi′,xi′ (1leqyi,yi′leqH かつ 1leqxi,xi′leqW) を出力せよ。 ただし、これはマス (yi,xi) にあるコインのうち 1 枚を上下左右に隣接するマス (yi′,xi′) に移動させる操作を表す。
問題文中の操作でないような操作が与えられた場合や、出力の形式が正しくない場合には Wrong Answer となるので注意せよ。
入力例 1
出力例 1
次のように操作を行えば、全てのマスに置かれたコインの数を偶数にできます。
- マス (2,2) に置かれているコインのうち 1 枚をマス (2,3) に移動します
- マス (1,1) に置かれているコインのうち 1 枚をマス (1,2) に移動します
- マス (1,3) に置かれているコインのうち 1 枚をマス (1,2) に移動します
入力例 2
出力例 2
入力例 3
出力例 3