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

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

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