B - アメーバ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

N マス、横 M マスの盤面がある。 上から i (1≦i≦N) マス目、左から j (1≦j≦M) マス目の位置を (i,j) と表す。

はじめ、マス (i,j) には a_{ij} 匹のアメーバがいた。 ただし、盤面の端にアメーバはいなかった。 すなわち、i=1,N または j=1,M ならば a_{ij}=0 である。

高橋君が大声を出すと、アメーバたちは驚いてそれぞれ次の行動をとった。

  • 1 匹のアメーバが 4 匹に分裂し、上下左右のマスへ 1 匹ずつ移動した。

その結果、マス (i,j) には b_{ij} 匹のアメーバがいることになった。

今のアメーバの配置 (b_{ij}) が与えられるので、はじめのアメーバの配置 (a_{ij})1 つ求めよ。 ただし、(a_{ij}) は少なくとも 1 つ存在する。


入力

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

N M
b_{11}b_{12}..b_{1M}
b_{21}b_{22}..b_{2M}
:
b_{N1}b_{N2}..b_{NM}
  • 1 行目には、盤面の縦のマス数 N (3≦N≦500) と横のマス数 M (3≦M≦500) が空白区切りで与えられる。
  • 2 行目からの N 行には、今のアメーバの配置が与えられる。このうち i 行目の j 文字目の数字が b_{ij} (0≦b_{ij}≦9) を表す。

出力

はじめのアメーバの配置を 1 つ、以下の形式で N 行に出力せよ。 ただし、i 行目の j 文字目の数字が a_{ij} を表す。 出力の末尾に改行を入れること。

a_{11}a_{12}..a_{1M}
a_{21}a_{22}..a_{2M}
:
a_{N1}a_{N2}..a_{NM}

入力例1

3 3
010
101
010

出力例1

000
010
000

入力例2

3 4
0230
2323
0230

出力例2

0000
0230
0000

入力例3

5 5
00100
03040
20903
05060
00300

出力例3

00000
00100
02030
00300
00000