MZL is an active boy.One day,he is playing a game with DSY and GTW.
The combat happened in a chessboard which has R rows and C columns.every grid has a parent.the parent of gird (x,y) is (x−1,y−1).the parent of grid (1,y) is (1,y−1) and the parent of grid (x,1) is (x−1,1),(1,1)has no parent.
Let's define x is the ancestor of y while one of the following conditions meets:
2.x is the parent of an ancestor of y
Initially the nodes in the chessboard are either white or black.Every player takes turns to act.In each turn,the player can choose a white node and choose one of its ancestors,then the nodes which lies in the path from the chosen node to the chosen ancestor flip its color(white into black,black into white),the player who cannot act loses the game.GTW takes the first turn.
Suppose the two players act optimally,DSY wonders whether he will win the game.
In consideration of the large size of the chessboard.DSY gives a list of rectangles ,the initial white nodes is the union of the rectangles.
the test data consists several cases.Please read until EOF.
the first line are 3 integers n,R,C,means the list size of the rectangles,the number of the rows and the number of the columns.
next n lines ,each line has 4 integers,x1,y1,x2,y2,means the upper left and the lower right nodes of the rectangle.
And there are 8 big test cases and 8 small test cases
if dsy has a strategy to win,print "DSY wins",otherwise,print "GTW wins"
3 3 3 1 1 3 3 2 1 3 3 2 1 3 1 1 3 3 1 3 2 3
GTW wins DSY wins