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

Довідка з шахів:
\begin{itemize}
\item\textbf{Шах} --- тактичний хід, при якому проходить напад на короля суперника.

\item\textbf{Мат} --- ситуація, коли король опиняється під шахом, і у гравця нема жодного можливого ходу, після якого король перестав би перебувати під шахом.

\item\textbf{Пат} --- становище, коли сторона, котра повинна ходити, не може це зробити, бо всі її фігури позбавлені можливості зробити хід, при цьому король не перебуває під шахом.
\end{itemize}
Правила ударів/ходів фігур в рамках задачі:

\begin{itemize}

\item\textbf{Королева} --- б'є по вертикалях, діагоналях та горизонталях, на яких вона перебуває, але вона не може перескакувати через інші фігури.

\includegraphics[width=4cm]{queen.png}


\item\textbf{Тура} --- б'є по вертикалях та горизонталях, на яких вона перебуває, але не може перескакувати через інші фігури.

\includegraphics[width=4cm]{tura.png}

\item\textbf{Слон} --- б'є по діагоналях, на яких він перебуває, але не може перескакувати через інші фігури.

\includegraphics[width=4cm]{slon.png}

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

\includegraphics[width=4cm]{knight.png}

\item\textbf{Пішак} --- б'є по діагоналі на одну клітинку в сторону суперника (таким чином білі пішаки завжди б'ють тільки по діагоналі вгору).

\includegraphics[width=4cm]{pishak.png}

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

\includegraphics[width=4cm]{king.png}
\end{itemize}