Создать последовательность
Ваш следующий продукт — это новая игра, представляющая собой трехмерную версию классической игры "Крестики-нолики". Два игрока размещают шары в трехмерном пространстве (на доске) и стремятся создать ряд определенной длины.
Люди считают эту игру увлекательной, но пока не могут определиться с оптимальными значениями некоторых параметров. Например, какой размер доски делает игру наиболее интересной? Параметры, которые обсуждаются, это размер доски (обозначим его как n) и длина рядка (m). Чтобы определить эти параметры, вам предлагается создать компьютерный симулятор игры.
На Рисунках 1-3 показаны несколько примеров игры, соответствующих трем наборам данных из Примера Ввода.
Рисунок 1. Игра с n=m=3
Рисунок 2. Игра с n=m=3 (Белые сделали рядок из 3 раньше Черных)
Рисунок 3. Игра с n=4 m=3 (Черные сделали два рядка из 4)
Вот точные правила игры.
Два игрока, Черные и Белые, играют поочередно. Черные ходят первыми.
Имеется n×n вертикальных штырей. Каждый штырь может вместить до n шаров. Штырь определяется по его x- и y-координатам (1 ≤ x, y ≤ n). Шар на штыре определяется по его z-координате (1 ≤ z ≤ n). В начале игры штыри пусты.
В свой ход игрок выбирает один из n×n штырей и кладет шар своего цвета. Шар подчиняется закону гравитации, оставаясь прямо над самым верхним шаром на штыре или на полу (если штырь пуст). Иными словами, игрок выбирает x- и y-координаты, но не z-координату.
Цель игры — создать m-рядок. Если игрок создает m-рядок или более длинный рядок своего цвета, он выигрывает. m-рядок — это последовательность из m шаров одного цвета. Например, черные шары в позициях (5, 1, 2), (5, 2, 2) и (5, 3, 2) образуют 3-рядок. Рядок может быть горизонтальным, вертикальным или диагональным. Всего существует 13 возможных направлений для создания рядка, которые классифицируются следующим образом.
Одномерные оси. Например, (3, 1, 2), (4, 1, 2) и (5, 1, 2) образуют 3-рядок. В этой категории три направления.
Двумерные диагонали. Например, (2, 3, 1), (3, 3, 2) и (4, 3, 3) образуют 3-рядок. В этой категории шесть направлений.
Трехмерные диагонали. Например, (5, 1, 3), (4, 2, 4) и (3, 3, 5) образуют 3-рядок. В этой категории четыре направления.
Обратите внимание, что противоположные направления не различаются.
В процессе оценки игры люди играли в нее несколько раз, меняя значения параметров. Вам даны записи этих игр. Ваша задача — написать программу, которая определяет победителя каждой записанной игры.
Поскольку человеку сложно находить трехмерные рядки, игроки часто не замечают окончания игры и продолжают играть. В таких случаях ходы после определения победителя должны быть проигнорированы. Например, после победы игрока, создавшего m-рядок, игроки могут создать дополнительные m-рядки. В этом случае все m-рядки, кроме первого, игнорируются, и победитель не изменяется.
Игра может закончиться вничью, если не осталось штырей для размещения шаров. Также игра может быть завершена без создания m-рядка, что тоже считается ничьей.
Входные данные
Ввод состоит из нескольких наборов данных, каждый из которых соответствует записи игры. Набор данных начинается с строки, содержащей три положительных целых числа n, m и p, разделенных пробелом. Условия: 3 <= m <= n <= 7 и 1 <= p <= n^3. n и m — это параметры игры, как описано выше. p — количество ходов в игре.
Остальная часть набора данных состоит из p строк, каждая из которых содержит два положительных целых числа x и y. Каждая строка описывает ход, то есть игрок кладет шар на указанный штырь. Предполагается, что 1 <= x <= n и 1 <= y <= n. Также предполагается, что на одном штыре размещается не более n шаров.
Конец ввода обозначается строкой с тремя нулями, разделенными пробелом.
Выходные данные
Для каждого набора данных выведите строку, описывающую победителя и количество ходов до окончания игры. Победитель — это либо "Black", либо "White". Между победителем и количеством ходов должен быть один пробел. Никаких других символов в выводе быть не должно.
В случае ничьей строка вывода должна быть "Draw".