#abc302b. [abc302_b]Find snuke

[abc302_b]Find snuke

問題文

HH マス times\\timesWW マスのマス目があり、各マスに 11 つずつ英小文字が書き込まれています。 上から ii 行目かつ左から jj 列目のマスを (i,j)(i,j) で表します。

マス目に書き込まれている英小文字は HH 個の長さ WW の文字列 S1,S2,ldots,SHS_1,S_2,\\ldots, S_H によって与えられ、 SiS_ijj 文字目が、(i,j)(i, j) に書き込まれた英小文字を表します。

マス目の中に、s, n, u, k, eこの順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる 場所がただ 11 つ存在します。
そのような場所を見つけ、そのマスの位置を出力の形式に従って出力してください。

ただし、s, n, u, k, eこの順に(縦・横・ななめのいずれかの方向に) 連続して並んでいる場所とは、 55 つのマスの組 (A1,A2,A3,A4,A5)(A_1,A_2,A_3,A_4,A_5) であって、次をすべてみたすものをさします。

  • A1,A2,A3,A4,A5A_1,A_2,A_3,A_4,A_5 に書き込まれた英小文字はそれぞれ s, n, u, k, e である。
  • 1leqileq41\\leq i\\leq 4 について、AiA_iAi+1A_{i+1} は頂点または辺を共有している。
  • A1,A2,A3,A4,A5A_1,A_2,A_3,A_4,A_5 の中心はこの順に一直線上に等間隔で並んでいる。

制約

  • 5leqHleq1005\\leq H\\leq 100
  • 5leqWleq1005\\leq W\\leq 100
  • H,WH,W は整数
  • SiS_i は英小文字のみからなる長さ WW の文字列
  • 与えられるマス目の中に条件をみたす場所がただ 11 つ存在する

入力

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

HH WW S1S_1 S2S_2 vdots\\vdots SHS_H

出力

次の形式にしたがって、55 行出力せよ。

条件をみたす場所のうち s, n, u, k, e が書かれたマスがそれぞれ (R1,C1),(R2,C2)ldots,(R5,C5)(R_1,C_1), (R_2,C_2)\\ldots,(R_5,C_5) であるとき、 ii 行目には RiR_iCiC_i をこの順に空白区切りで出力せよ。

すなわち、以下のように出力せよ。

R1R_1 C1C_1 R2R_2 C2C_2 vdots\\vdots R5R_5 C5C_5

以下の入力例も参考にせよ。


入力例 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

出力例 1

5 2
5 3
5 4
5 5
5 6

この時、$(A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6))$ とすると、
それぞれのマスに書き込まれた英小文字は s, n, u, k, e であり、
1leqileq41\\leq i\\leq 4 について、AiA_iAi+1A_{i+1} は辺を共有しており、
各マスの中心は一直線上に存在するため、条件をみたしています。


入力例 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

出力例 2

5 5
4 4
3 3
2 2
1 1

$(A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1))$ が条件をみたしています。
例えば、$(A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1))$ は、1,21,2 つめの条件をみたしていますが、
マスの中心が一直線上に存在しないため、33 つめの条件をみたしていません。


入力例 3

10 10
kseeusenuk
usesenesnn
kskekeeses
nesnusnkkn
snenuuenke
kukknkeuss
neunnennue
sknuessuku
nksneekknk
neeeuknenk

出力例 3

9 3
8 3
7 3
6 3
5 3