103021: [Atcoder]ABC302 B - Find snuke

Problem Statement

There is a grid with $H$ horizontal rows and $W$ vertical columns. Each cell has a lowercase English letter written on it. We denote by $(i, j)$ the cell at the $i$-th row from the top and $j$-th column from the left.

The letters written on the grid are represented by $H$ strings $S_1,S_2,\ldots, S_H$, each of length $W$. The $j$-th letter of $S_i$ represents the letter written on $(i, j)$.

There is a unique set of contiguous cells (going vertically, horizontally, or diagonally) in the grid with s, n, u, k, and e written on them in this order.
Find the positions of such cells and print them in the format specified in the Output section.

A tuple of five cells $(A_1,A_2,A_3,A_4,A_5)$ is said to form a set of contiguous cells (going vertically, horizontally, or diagonally) with s, n, u, k, and e written on them in this order if and only if all of the following conditions are satisfied.

• $A_1,A_2,A_3,A_4$ and $A_5$ have letters s, n, u, k, and e written on them, respectively.
• For all $1\leq i\leq 4$, cells $A_i$ and $A_{i+1}$ share a corner or a side.
• The centers of $A_1,A_2,A_3,A_4$, and $A_5$ are on a common line at regular intervals.

Constraints

• $5\leq H\leq 100$
• $5\leq W\leq 100$
• $H$ and $W$ are integers.
• $S_i$ is a string of length $W$ consisting of lowercase English letters.
• The given grid has a unique conforming set of cells.

Input

The input is given from Standard Input in the following format:

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

Output

Print five lines in the following format.

Let $(R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5)$ be the cells in the sought set with s, n, u, k, and e written on them, respectively. The $i$-th line should contain $R_i$ and $C_i$ in this order, separated by a space.

In other words, print them in the following format:

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

See also Sample Inputs and Outputs below.

Sample Input 1

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Sample Output 1

5 2
5 3
5 4
5 5
5 6

Tuple $(A_1,A_2,A_3,A_4,A_5)=((5,2),(5,3),(5,4),(5,5),(5,6))$ satisfies the conditions.
Indeed, the letters written on them are s, n, u, k, and e;
for all $1\leq i\leq 4$, cells $A_i$ and $A_{i+1}$ share a side;
and the centers of the cells are on a common line.

Sample Input 2

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Sample Output 2

5 5
4 4
3 3
2 2
1 1

Tuple $(A_1,A_2,A_3,A_4,A_5)=((5,5),(4,4),(3,3),(2,2),(1,1))$ satisfies the conditions.
However, for example, $(A_1,A_2,A_3,A_4,A_5)=((3,5),(4,4),(3,3),(2,2),(3,1))$ violates the third condition because the centers of the cells are not on a common line, although it satisfies the first and second conditions.

Sample Input 3

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

Sample Output 3

9 3
8 3
7 3
6 3
5 3

问题描述

有一个网格，有$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\leq i\leq 4$，单元格$A_i$和$A_{i+1}$共享一个角落或边。
• $A_1,A_2,A_3,A_4$和$A_5$的中心在同一直线上，间隔相等。

约束

• $5\leq H\leq 100$
• $5\leq W\leq 100$
• $H$和$W$是整数。
• $S_i$是一个长度为$W$的字符串，由小写英文字母组成。
• 给定的网格有一个符合要求的单元格集合。

输入

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

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

输出

按照以下格式打印五行。

令$(R_1,C_1), (R_2,C_2)\ldots,(R_5,C_5)$是满足条件的单元格集合，上面依次写着s、n、u、k和e。 第$i$行应包含$R_i$和$C_i$，用一个空格隔开。

换句话说，按照以下格式打印它们：

$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_5$ $C_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；
对于所有的$1\leq i\leq 4$，单元格$A_i$和$A_{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))$违反了第三个条件，因为单元格的中心不在同一直线上，尽管它满足了第一个和第二个条件。

样例输入 3

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

样例输出 3

9 3
8 3
7 3
6 3
5 3