Row and Column Deletion Game

Time limit1sMemory limit128 MB

Summary

Given an n x n matrix where players alternately remove the last row or column if its sum is even, determine which player wins with optimal play across possibly many test cases up to n=1000.

Level: Medium6 of 10
Topics: Game theory, Dynamic programming, Matrix
Solved: No attempts yet

Problem

Bill loves computer games and enjoys finding efficient solutions to them. He is now studying the following game.

The game starts with an $n \times n$ matrix filled with positive integers. On their turn, a player may delete the last row or the last column of the current matrix, but only if the sum of the numbers in that row or column is even. A player who, on their turn, can delete neither the last row nor the last column loses the game.

Bill wants to classify each game as a first-player win (W) or a first-player loss (L). "First player wins" means the first player has a strategy that guarantees a win no matter how the second player plays. "First player loses" means that whatever the first player does, the second player has a winning strategy.

Bill is also a skilled programmer and wants a program that classifies a game quickly. Can you help him?

Input

Several games are given one after another and are read from standard input.

Each game is given by the number $n$ ( $n \le 1000$ ), the size of the matrix, followed by the $n \times n$ positive integers of the matrix (given row by row). Whitespace (spaces and newlines) may appear freely between numbers. The input is well-formed and ends at end of file.

Output

For each game, print W if the first player wins or L if the first player loses, each on its own line.

Examples1

Example 1
Input
```
2
2 4
6 8
3
5 4 2 
1 5 9 
7 3 8
```
Expected output
```
L
W
```