寻找 snuke

题目描述

有一个 $H$ 行 $W$ 列的网格，每个格子中写有一个小写英文字母。 我们用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

网格上写的字母用 $H$ 个长度为 $W$ 的字符串 $S_1,S_2,\ldots,S_H$ 表示。 $S_i$ 的第 $j$ 个字符表示写在 $(i,j)$ 上的字母。

网格中存在唯一一组连续的格子（向竖直、水平或对角方向），上面依次写着 s、n、u、k、e。

请找出这些格子的位置，并按「输出格式」一节中规定的格式输出。

五个格子的元组 $(A_1,A_2,A_3,A_4,A_5)$ 被称为一组依次写着 s、n、u、k、e 的连续格子（向竖直、水平或对角方向），当且仅当满足以下所有条件：

• $A_1,A_2,A_3,A_4$ 和 $A_5$ 上分别写着 s、n、u、k 和 e。
• 对于所有 $1 \le i \le 4$，格子 $A_i$ 与 $A_{i+1}$ 共边或共角。
• $A_1,A_2,A_3,A_4,A_5$ 的中心在同一条直线上，且相邻间距相等。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$
$S_1$
$S_2$
$\vdots$
$S_H$

输出格式

按以下格式输出五行。

设所求格子组中依次写着 s、n、u、k、e 的格子分别为 $(R_1,C_1),(R_2,C_2),\ldots,(R_5,C_5)$。 第 $i$ 行按顺序输出 $R_i$ 和 $C_i$，用空格分隔。

即，按以下格式输出：

$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_5$ $C_5$

样例

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

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；

对于所有 $1 \le i \le 4$，格子 $A_i$ 与 $A_{i+1}$ 共边；

且这些格子的中心在同一条直线上。

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

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))$ 虽然满足第一、第二个条件，但因为格子的中心不在同一条直线上，违反了第三个条件。

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

9 3
8 3
7 3
6 3
5 3

数据范围

• $5 \le H \le 100$
• $5 \le W \le 100$
• $H$ 和 $W$ 均为整数。
• $S_i$ 是长度为 $W$、由小写英文字母组成的字符串。
• 给定网格中存在唯一一组符合条件的格子。