|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||128 MB||4||4||4||100.000%|
Your company’s next product will be a new game, which is a three-dimensional variant of the classic game “Tic-Tac-Toe”. Two players place balls in a three-dimensional space (board), and try to make a sequence of a certain length.
People believe that it is fun to play the game, but they still cannot fix the values of some parameters of the game. For example, what size of the board makes the game most exciting? Parameters currently under discussion are the board size (we call it n in the following) and the length of the sequence (m). In order to determine these parameter values, you are requested to write a computer simulator of the game.
You can see several snapshots of the game in Figures 3–5. These figures correspond to the three datasets given in the Sample Input.
Figure 3: A game with n = m = 3
Here are the precise rules of the game
Figure 4: A game with n = m = 3 (White made a 3-sequence before Black)
A sequence can be horizontal, vertical, or diagonal. Precisely speaking, there are 13 possible directions to make a sequence, categorized as follows.
Figure 5: A game with n = 4, m = 3 (Black made two 4-sequences)
Note that we do not distinguish between opposite directions.
As the evaluation process of the game, people have been playing the game several times changing the parameter values. You are given the records of these games. It is your job to write a computer program which determines the winner of each recorded game.
Since it is difficult for a human to find three-dimensional sequences, players often do not notice the end of the game, and continue to play uselessly. In these cases, moves after the end of the game, i.e. after the winner is determined, should be ignored. For example, after a player won making an m-sequence, players may make additional m-sequences. In this case, all m-sequences but the first should be ignored, and the winner of the game is unchanged.
A game does not necessarily end with the victory of one of the players. If there are no pegs left to put a ball on, the game ends with a draw. Moreover, people may quit a game before making any m-sequence. In such cases also, the game ends with a draw.
The input consists of multiple datasets each corresponding to the record of a game. A dataset starts with a line containing three positive integers n, m, and p separated by a space. The relations 3 ≤ m ≤ n ≤ 7 and 1 ≤ p ≤ n3 hold between them. n and m are the parameter values of the game as described above. p is the number of moves in the game.
The rest of the dataset is p lines each containing two positive integers x and y. Each of these lines describes a move, i.e. the player on turn puts his ball on the peg specified. You can assume that 1 ≤ x ≤ n and 1 ≤ y ≤ n. You can also assume that at most n balls are put on a peg throughout a game.
The end of the input is indicated by a line with three zeros separated by a space.
For each dataset, a line describing the winner and the number of moves until the game ends should be output. The winner is either “Black” or “White”. A single space should be inserted between the winner and the number of moves. No other extra characters are allowed in the output.
In case of a draw, the output line should be “Draw”.
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
Draw White 6 Black 15
ICPC > Regionals > Asia Pacific > Japan > Asia Regional Contest 2004 in Ehime B번