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

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

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

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

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

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

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

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

  

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

  

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

  

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

  

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

  

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

  

Note

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

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

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

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

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

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