Шахова проблема

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

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

• Шах — тактичний хід, при якому проходить напад на короля суперника.

• Мат — ситуація, коли король опиняється під шахом, і у гравця нема жодного можливого ходу, після якого король перестав би перебувати під шахом.

• Пат — становище, коли сторона, котра повинна ходити, не може це зробити, бо всі її фігури позбавлені можливості зробити хід, при цьому король не перебуває під шахом.

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

• Королева — б'є по вертикалях, діагоналях та горизонталях, на яких вона перебуває, але вона не може перескакувати через інші фігури.

  

• Тура — б'є по вертикалях та горизонталях, на яких вона перебуває, але не може перескакувати через інші фігури.

  

• Слон — б'є по діагоналях, на яких він перебуває, але не може перескакувати через інші фігури.

  

• Кінь — хід конем складається строго з двох пересувань: на одне поле по вертикалі чи горизонталі, потім віддаляючись від вихідного поля на одне поле по діагоналі. Це єдина фігура, яка може перескакувати через інші фігури.

  

• Пішак — б'є по діагоналі на одну клітинку в сторону суперника (таким чином білі пішаки завжди б'ють тільки по діагоналі вгору).

  

• Король — пересувається зі свого поля на одне з вільних суміжних полів (у тому числі й по діагоналі), що не перебуває під ударом фігур суперника. Може бити фігуру, яка знаходиться на суміжному полі, якщо вона не під ударом.

  

Вхідні дані

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

• символ «.» позначає пусту клітинку

• символ «p» позначає пішака

• символ «r» позначає туру

• символ «n» позначає коня

• символ «b» позначає слона

• символ «Q» позначає королеву

• символ «K» позначає короля

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

Вихідні дані

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

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

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

Приклади

Примітка

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

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

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

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

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

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