Зробіть Послідовність

Наступний продукт вашої компанії — це нова гра, яка є тривимірною версією класичної гри "Хрестики-нулики". Два гравці розміщують кулі в тривимірному просторі (на дошці) і намагаються створити рядок певної довжини.

Люди вважають, що грати в цю гру весело, але вони ще не визначилися з деякими параметрами гри. Наприклад, який розмір дошки робить гру найбільш захоплюючою? Параметри, які зараз обговорюються, — це розмір дошки (ми називаємо його $n$) і довжина рядка ($m$). Щоб визначити ці значення параметрів, вам потрібно написати комп'ютерний симулятор гри.

Ви можете побачити кілька знімків гри на Рисунках 1–3. Ці рисунки відповідають трьом наборам даних, наведеним у Прикладі Вводу.

Рисунок 1. Гра з n=m=3

Рисунок 2. Гра з n=m=3 (Білий створив 3-рядок перед Чорним)

Рисунок 3. Гра з n=4, m=3 (Чорний створив два 4-рядки)

Ось точні правила гри.

1. Два гравці, Чорний і Білий, грають по черзі. Чорний грає першим.

2. Існує n\times n вертикальних стержнів. Кожен стержень може вмістити до $n$ куль. Стержень можна визначити за його $x$- та $y$-координатами (1 \le x, y \le n). Куля на стержні може бути визначена за її $z$-координатою (1 \le z \le n). На початку гри на жодному з стержнів немає куль.

3. У свій хід гравець вибирає один з n\times n стержнів і кладе кулю свого кольору на стержень. Куля підкоряється закону гравітації. Тобто, куля залишається прямо над найвищою кулею на тому ж стержні або на підлозі (якщо на стержні немає куль). Іншими словами, гравець може вибрати $x$- та $y$-координати кулі, але він не може вибрати її $z$-координату.

4. Мета гри — створити $m$-рядок. Якщо гравець створює $m$-рядок або довший свого кольору, він виграє. $m$-рядок — це рядок з $m$ послідовних куль одного кольору. Наприклад, чорні кулі на позиціях (5, 1, 2), (5, 2, 2) і (5, 3, 2) утворюють 3-рядок. Рядок може бути горизонтальним, вертикальним або діагональним. Точніше кажучи, існує $13$ можливих напрямків для створення рядка, які класифікуються наступним чином:

   1. Одновимірні осі. Наприклад, (3, 1, 2), (4, 1, 2) і (5, 1, 2) — це 3-рядок. У цій категорії є три напрямки.

   2. Двовимірні діагоналі. Наприклад, (2, 3, 1), (3, 3, 2) і (4, 3, 3) — це 3-рядок. У цій категорії є шість напрямків.

   3. Тривимірні діагоналі. Наприклад, (5, 1, 3), (4, 2, 4) і (3, 3, 5) — це 3-рядок. У цій категорії є чотири напрямки.

Зверніть увагу, що ми не розрізняємо протилежні напрямки.

Як частина процесу оцінки гри, люди грали в гру кілька разів, змінюючи значення параметрів. Вам надано записи цих ігор. Ваше завдання — написати комп'ютерну програму, яка визначає переможця кожної записаної гри.

Оскільки людині важко знайти тривимірні рядки, гравці часто не помічають закінчення гри і продовжують грати даремно. У таких випадках ходи після закінчення гри, тобто після визначення переможця, слід ігнорувати. Наприклад, після того, як гравець виграв, створивши $m$-рядок, гравці можуть створити додаткові $m$-рядки. У цьому випадку всі $m$-рядки, крім першого, слід ігнорувати, і переможець гри не змінюється.

Гра не обов'язково закінчується перемогою одного з гравців. Якщо не залишилося стержнів, на які можна покласти кулю, гра закінчується внічию. Крім того, люди можуть припинити гру до створення будь-якого $m$-рядка. У таких випадках гра також закінчується внічию.