На екзамені з алгоритмів Петрик витягнув нещасливу задачу, тому вельми просить вашої допомоги. Перед вами стандартна шахова дошка $$$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$$$. Крім того будь-який хід короля залишить його під шахом, що створює мат.
Ілюстрація до третього приклада.