На екзамені з алгоритмів Петрик витягнув нещасливу задачу, тому вельми просить вашої допомоги. Перед вами стандартна шахова дошка $$$8 \times 8$$$, клітинки якої пронумеровані зліва направо від $$$a$$$ до $$$h$$$ та знизу вгору від $$$1$$$ до $$$8$$$. Серед білих фігур дошці можуть бути всі види фігур, крім короля, а серед чорних навпаки — є лише один король. Також відомо що фігури розставлені абсолютно довільно, тобто їх розміщення може не підпорядковуватись стандартним правилам шахів (білі навіть можуть мати забагато фігур певного типу). Вашою задачею є визначити, у якому положенні знаходиться чорний гравець: мат, пат чи звичайне положення.
Довідка з шахів:
- Шах — тактичний хід, при якому проходить напад на короля суперника.
- Мат — ситуація, коли король опиняється під шахом, і у гравця нема жодного можливого ходу, після якого король перестав би перебувати під шахом.
- Пат — становище, коли сторона, котра повинна ходити, не може це зробити, бо всі її фігури позбавлені можливості зробити хід, при цьому король не перебуває під шахом.
- Королева — б'є по вертикалях, діагоналях та горизонталях, на яких вона перебуває, але вона не може перескакувати через інші фігури.
- Тура — б'є по вертикалях та горизонталях, на яких вона перебуває, але не може перескакувати через інші фігури.
- Слон — б'є по діагоналях, на яких він перебуває, але не може перескакувати через інші фігури.
- Кінь — хід конем складається строго з двох пересувань: на одне поле по вертикалі чи горизонталі, потім віддаляючись від вихідного поля на одне поле по діагоналі. Це єдина фігура, яка може перескакувати через інші фігури.
- Пішак — б'є по діагоналі на одну клітинку в сторону суперника (таким чином білі пішаки завжди б'ють тільки по діагоналі вгору).
- Король — пересувається зі свого поля на одне з вільних суміжних полів (у тому числі й по діагоналі), що не перебуває під ударом фігур суперника. Може бити фігуру, яка знаходиться на суміжному полі, якщо вона не під ударом.
Вхідні дані містять $$$8$$$ рядків, кожен з яких складається з $$$8$$$ символів. Кожен символ задає відповідну клітинку шахової дошки:
- символ «.» позначає пусту клітинку
- символ «p» позначає пішака
- символ «r» позначає туру
- символ «n» позначає коня
- символ «b» позначає слона
- символ «Q» позначає королеву
- символ «K» позначає короля
Гарантується, що є рівно один король.
У випадку мату у першому рядку виведіть «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$$$. Крім того будь-який хід короля залишить його під шахом, що створює мат.
Ілюстрація до третього приклада.