Game#1400
Bill is fond of computer games. He enjoys analyzing games and finding efficient solutions. He is currently studying the following game.
The game begins with an n \times n matrix filled with positive integers. On each turn, a player may delete the last row or the last column of the matrix if the sum of the numbers in that row or column is even. If a player cannot delete either the last row or the last column on their turn, they lose the game.
Bill wants to classify each game as either a win for the first player (W) or a loss for the first player (L). "First player wins" means the first player has a strategy to win regardless of how the second player acts. "First player loses" means that, no matter what the first player does, the second player has a strategy to win.
Bill, also a skilled programmer, wants to quickly classify the game using a program. Can you help him?
Input is provided from a text file. Each dataset describes a particular game. A dataset starts with the number (n \leq 1000), the matrix size, followed by the n \times n positive integers filling the matrix.
White spaces may appear freely in the input. The input is correct and ends with end-of-file. For each dataset, the program prints the result (W or L) to the standard output, starting from the beginning of a new line.
For each dataset, print W if the first player wins, or L if the first player loses.
Beispiel
2
2 4
6 8LBeispiel 1
In the example, the matrix size is . The matrix is: 2 4 6 8 The result for this dataset is L, meaning that no matter what the first player does, the second player wins.