Typhoon

Time Limit : 5 sec, Memory Limit : 262144 KB

E : 台風 / Typhoon

問題文

南北方向に H ,東西方向に W の大きさの町がある. 町には一辺の長さが 1 の正方形の区画に隙間なく整備されており,全ての区画に 1 軒ずつ家が建っている.

この町のある区画の上空で台風が発生し,被害を与えた後,ある区画の上空で温帯低気圧に変化した. 変化した後は被害を与えない. 下図のように,台風は高さ 3, 幅 3 の正方形であり, ★のついたマスを中心と呼ぶことにする.台風は 8 近傍に区画単位で移動する. つまり,台風の中心は辺または頂点を共有する区画(現在の区画を含む)に移るように,全体を伴って移動する. ただし,町の外に台風がはみ出ることはなく, 台風の中心は,下の図の網掛けのように,北から 0 番目と H − 1 番目,西から 0 番目と W − 1 番目の区間は通らないように移動する.

家は台風が一度上空に来ると,以下のように被害の程度が変化する.

損壊ナシ → 一部損壊 → 半壊 → 全壊 → 跡形ナシ

だが,幸い跡形ナシとなった家は無かったようだ. 各家の被害の状況が与えられるので,台風が発生した地点と,温帯低気圧に変化した地点を求めよ. ただし,発生した区画を北から s_i 番目,西から s_j 番目, 温帯低気圧に変化した区画を北から t_i 番目,西から t_j 番目とすると, 2 つの地点は 10000 t_i + t_j 10000 s_i + s_j を満たすように定まる.

入力

H \ W
D_{11} \ … \ D_{1W}
D_{21} \ … \ D_{2W}

D_{H1} \ … \ D_{HW}

D_{ij} は北から i 番目, 西から j 番目の家の被害の程度を以下のように表す整数である.

  • 0 : 損壊ナシ
  • 1 : 一部損壊
  • 2 : 半壊
  • 3 : 全壊

制約

  • 整数である
  • 入力は答えが一意に定まるようなもののみ与えられる
  • 3 ≤ H,W ≤ 500
  • 0 ≤ D_{ij} ≤ 3

出力

答えを以下のように 1 行で出力せよ.

s_i \ s_j \ t_i \ t_j

サンプル

サンプル入力1

7 5
0 0 0 0 0
0 1 1 1 0
0 2 2 2 0
0 3 3 3 0
0 2 2 2 0
0 1 1 1 0
0 0 0 0 0

サンプル出力1

4 2 2 2

サンプル入力2

6 6
0 0 0 1 1 1
0 0 0 2 2 2
0 0 1 3 3 2
1 2 3 3 2 1
1 2 3 2 1 0
1 2 2 1 0 0

サンプル出力2

4 1 1 4

サンプル入力3

4 4
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0

サンプル出力3

1 1 1 1

Source: Aizu Competitive Programming Camp 2015 Day1 , Japan, 2015-09-21