公司的下一个产品将是一款新游戏,它是经典游戏“井字棋”(Tic-Tac-Toe)的三维变体。两名玩家在三维空间(棋盘)中放置球,并试图连成特定长度的序列。
人们认为玩这个游戏很有趣,但他们仍然无法确定游戏的一些参数值。例如,多大的棋盘尺寸会让游戏最令人兴奋?目前正在讨论的参数是棋盘尺寸(下文称为 $n$)和序列长度($m$)。为了确定这些参数值,需要你编写一个游戏计算机模拟器。
你可以在图 3-5 中看到游戏的几个快照。这些图对应于样例输入中给出的三个数据集。
图 3:$n = m = 3$ 的游戏
以下是该游戏的精确规则。
- 两名玩家,黑方(Black)和白方(White),轮流下棋。黑方先手。
- 棋盘上有 $n \times n$ 个垂直立柱。每个立柱最多可容纳 $n$ 个球。立柱可以通过其 $x$ 和 $y$ 坐标($1 \le x, y \le n$)来指定。立柱上的球可以通过其 $z$ 坐标($1 \le z \le n$)来指定。游戏开始时,所有立柱上都没有球。
图 4:$n = m = 3$ 的游戏(白方在黑方之前连成了 3-序列)
- 在自己的回合中,玩家选择 $n \times n$ 个立柱中的一个,并将自己颜色的球放入该立柱。球遵循重力定律。也就是说,球会停在同一立柱上最顶端的球的正上方,或者停在底板上(如果该立柱上没有球)。换句话说,玩家可以选择球的 $x$ 和 $y$ 坐标,但不能选择其 $z$ 坐标。
- 游戏的目标是连成一个 $m$-序列。如果一名玩家连成了长度为 $m$ 或更长的同色球序列,他就获胜。$m$-序列是指 $m$ 个连续的同色球。例如,位于 $(5, 1, 2)$、$(5, 2, 2)$ 和 $(5, 3, 2)$ 的黑球构成了一个 3-序列。序列可以是水平、垂直或对角线的。准确地说,共有 13 种可能的序列方向,分类如下:
图 5:$n = 4, m = 3$ 的游戏(黑方连成了两个 4-序列)
(a) 一维轴向。例如,$(3, 1, 2)$、$(4, 1, 2)$ 和 $(5, 1, 2)$ 是一个 3-序列。此类方向共有三种。 (b) 二维对角线。例如,$(2, 3, 1)$、$(3, 3, 2)$ 和 $(4, 3, 3)$ 是一个 3-序列。此类方向共有六种。 (c) 三维对角线。例如,$(5, 1, 3)$、$(4, 2, 4)$ 和 $(3, 3, 5)$ 是一个 3-序列。此类方向共有四种。
注意,我们不区分相反的方向。
作为游戏评估过程的一部分,人们在改变参数值的情况下多次进行了游戏。你将获得这些游戏的记录。你的任务是编写一个计算机程序,确定每场记录游戏中的获胜者。
由于人类很难发现三维序列,玩家往往没有注意到游戏已经结束,并继续进行无意义的落子。在这种情况下,游戏结束(即获胜者确定)之后的落子应该被忽略。例如,在一名玩家通过连成 $m$-序列获胜后,玩家可能会连成额外的 $m$-序列。在这种情况下,除第一个 $m$-序列外,所有后续的 $m$-序列都应被忽略,且游戏的获胜者保持不变。
游戏不一定以其中一名玩家的胜利而结束。如果棋盘上没有剩余空间放置球,游戏以平局结束。此外,人们可能在连成任何 $m$-序列之前就退出游戏。在这种情况下,游戏也以平局结束。
输入格式
输入包含多个数据集,每个数据集对应一场游戏的记录。数据集的第一行包含三个正整数 $n$、$m$ 和 $p$,中间用空格分隔。它们满足关系 $3 \le m \le n \le 7$ 和 $1 \le p \le n^3$。$n$ 和 $m$ 是如上所述的游戏参数值,$p$ 是游戏中的落子次数。
数据集的其余部分包含 $p$ 行,每行包含两个正整数 $x$ 和 $y$。每一行描述一次落子,即当前玩家将球放入指定的立柱。你可以假设 $1 \le x \le n$ 且 $1 \le y \le n$。你还可以假设在整个游戏过程中,每个立柱上最多放置 $n$ 个球。
输入的结尾由一行包含三个零的行表示,中间用空格分隔。
输出格式
对于每个数据集,输出一行,描述获胜者和游戏结束时的落子次数。获胜者为“Black”或“White”。获胜者和落子次数之间应插入一个空格。输出中不允许包含其他多余字符。
如果是平局,输出行应为“Draw”。
样例
样例输入 1
3 3 3 1 1 1 1 1 1 3 3 7 2 2 1 3 1 1 2 3 2 1 3 3 3 1 4 3 15 1 1 2 2 1 1 3 3 3 3 1 1 3 3 3 3 4 4 1 1 4 4 4 4 4 4 4 1 2 2 0 0 0
样例输出 1
Draw White 6 Black 15