Шахова проблема
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

На екзамені з алгоритмів Петрик витягнув нещасливу задачу, тому вельми просить вашої допомоги. Перед вами стандартна шахова дошка $$$8 \times 8$$$, клітинки якої пронумеровані зліва направо від $$$a$$$ до $$$h$$$ та знизу вгору від $$$1$$$ до $$$8$$$. Серед білих фігур дошці можуть бути всі види фігур, крім короля, а серед чорних навпаки — є лише один король. Також відомо що фігури розставлені абсолютно довільно, тобто їх розміщення може не підпорядковуватись стандартним правилам шахів (білі навіть можуть мати забагато фігур певного типу). Вашою задачею є визначити, у якому положенні знаходиться чорний гравець: мат, пат чи звичайне положення.

Довідка з шахів:

Правила ударів/ходів фігур в рамках задачі:

Вхідні дані

Вхідні дані містять $$$8$$$ рядків, кожен з яких складається з $$$8$$$ символів. Кожен символ задає відповідну клітинку шахової дошки:

Гарантується, що є рівно один король.

Вихідні дані

У випадку мату у першому рядку виведіть «Checkmate», а в наступних рядках виведіть клітинки всіх фігур, що завдають шах у довільному порядку.

У випадку пату у першому рядку виведіть «Stalemate».

В іншому випадку виведіть «Continue» та у довільному порядку всі клітинки, у які король може зробити хід.

Приклади

Вхідні дані
......K.
...r.pp.
......b.
pp..n.r.
....p...
.......p
...p.b.p
..Q..n..
Вихідні дані
Continue
g7
Вхідні дані
Kp......
p......r
........
.n......
........
........
p.pppppp
r.bQ.b..
Вихідні дані
Stalemate
Вхідні дані
r.......
.p...p.n
bbp.rp..
...KQr..
..p...r.
.p......
..p.pp..
...n....
Вихідні дані
Checkmate
c4
e5
Вхідні дані
........
......K.
.....ppp
........
........
........
........
..QQQQQQ
Вихідні дані
Continue
f8
g8
h8

Пояснення

У першому прикладі король може атакувати пішака на $$$g7$$$ та перейти туди, бо ця клітинка не перебуває під атакою жодної білої фігури.

Ілюстрація до першого приклада.

У другому прикладі король не знаходиться під шахом. У нього є три потенційно можливі ходи: $$$b8$$$, $$$b7$$$ та $$$a7$$$. Хід на $$$b8$$$ неможливий, бо це призведе до шаху від пішака на $$$a7$$$. Хід на $$$b7$$$ неможливий, бо це призведе до шаху від тури на $$$h7$$$. Хід на $$$a7$$$ неможливий, бо це призведе до шаху від тури на $$$h7$$$. Таким чином король не перебуває під шахом, але здійнити хід не може, що означає пат.

Ілюстрація до другого приклада.

У третьому прикладі король знаходиться під шахом, спричиненим пішаком на $$$c4$$$ та королевою на $$$e5$$$. Крім того будь-який хід короля залишить його під шахом, що створює мат.

Ілюстрація до третього приклада.