Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3259
Boring Game Between DD and Lanrete

Time Limit: 5 Seconds      Memory Limit: 32768 KB

DD and Lanrete are playing a boring game. As a programmer, DD decides to write a program to solve it! Below is everything you should know about the game.

A cube has N * N * N cells labeled from (0,0,0) to (N-1,N-1,N-1). Each cell has a value of 0 or 1. In this cube, there are M cells having the value of 1. The remaining cells in the cube have the values of 0. Two players play a game by making moves in turn until no more moves can be made. DD will make the move first. Each player can only make one move at each step. The player who cannot make a move loses and the other player wins the game. A legal move is an action to flip the value (from 0 to 1 or from 1 to 0) of eight cells at eight corners of a rectangular cuboid inside the cube which satisfies the following conditions:

  • Length of each eage of the rectangular cuboid must be larger than 1. In another word, each cell at the eight corner must be different from each other. For example, a 2x2x1 cuboid is not allowed, while a 2x2x2 cuboid is.
  • The cell with the highest coordinates among the eight cells must have the value of 1. For example, if the eight cells are (1,1,1), (1,1,3), (1,3,1), (1,3,3), (3,1,1), (3,1,3), (3,3,1) and (3,3,3), the cell with the highest coordinates is the cell (3,3,3) and it must have value of 1.

The input file consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each data set, the first line contains an integer N (0 < N <= 32) representing the size of the cube. The next line contains an integer M (0 < M <= 100) . Each of the next M lines contains three integers x,y,z (0 <= x,y,z, < n) separated by space representing the coordinates of a cell with the value of 1.


For each data test, write in one line "DD" if there exists a winning strategy for DD with the given cube or "Lanrete" otherwise.

Sample Input
6 4
0 1 0
4 4 3
2 4 2
3 5 4
6 3
0 1 0
4 4 3
2 4 2
Sample Output

Author: CUI, Tianyi
Source: ZOJ Monthly, November 2009
Submit    Status