12087. Знайти слово


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Існує сітка з \(H\) горизонтальних рядків і \(W\) вертикальних стовпців. У кожній клітинці написана мала англійська літера. Позначимо \((i,j)\) комірку в \(i\)-му рядку зверху та \(j\)-му стовпчику зліва.

Букви, написані на сітці, представлені \(H\) рядками \(S_1 ​,S_2 ​ ,…,S_H ​\), кожен довжиною \(W\). \(j\)-та літера \(S_i\) ​ представляє літеру, написану на \((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≤i≤4\) клітинки \(A_i\) ​ та \(A_{i+1}\) ​ мають спільний кут або сторону.
  • Центри \(A_1 ​, A_2 ​ , A_3 ​ , A_4, ​ A_5\) ​ лежать на одній прямій через рівні проміжки.

Обмеження

  • \(5≤H≤100\)
  • \(5≤W≤100\)
  • \(H\) і \(W\) є цілими числами.
  • \(S_i\) — рядок довжиною \(W\), що складається з малих англійських літер.
  • Дана сітка має унікальний відповідний набір комірок.

Формат вхідних даних

Перший рядок містить цілі числа \(H,W\).

Наступні  \(H\) рядків містять \(S_i\).

Формат вихідних даних

У вихідний потік виведіть п’ять рядків у такому форматі.

Нехай \((R_1 ​ , C_1 ​ ), (R_2 ​ , C_2 ​ ) …, (R_5 ​ , C_5 ​ )\) — клітинки з записами 's', 'n', 'u', 'k' та 'e' на них відповідно.

\(I\)-й рядок має містити \(R_i\) ​ та \(C_i\) ​ у такому порядку, розділених пробілом.

Приклад вхідних даних

6 6
vgxgpu
amkxks
zhkbpp
hykink
esnuke
zplvfj

Приклад вихідних даних

5 2
5 3
5 4
5 5
5 6

Приклад вхідних даних

5 5
ezzzz
zkzzz
ezuzs
zzznz
zzzzs

Приклад вихідних даних

5 5
4 4
3 3
2 2
1 1

Приклад вхідних даних

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

Приклад вихідних даних

9 3
8 3
7 3
6 3
5 3

Коментарі

Ще немає коментарів.