Problem3776--World of Darkraft

3776: World of Darkraft

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently Roma has become the happy owner of a new game World of Darkraft. This game combines elements of virtually all known genres, and on one of the later stages of the game Roma faced difficulties solving a puzzle.

In this part Roma fights with a cunning enemy magician. The battle takes place on a rectangular field plaid n×m. Each cell contains one magical character: L, R or X. Initially all the squares of the field are "active".

The players, Roma and enemy magician, take turns. Roma makes the first move. During a move a player selects one of the active cells. Then depending on the image in the character in the cell one of the following actions takes place:

  • L − magical waves radiate from the cell to the left downwards and to the right upwards along diagonal paths. All cells on the path of the waves (including the selected cell too) become inactive. The waves continue until the next inactive cell or to the edge of the field if there are no inactive cells on the way.
  • R − the magical waves radiate to the left upwards and to the right downwards.
  • X − the magical waves radiate in all four diagonal directions.

If the next player cannot make a move (i.e., all cells are inactive), he loses.

Roma has been trying to defeat the computer opponent for three days but he just keeps losing. He asks you to help him and determine whether it is guaranteed that he can beat the opponent, or he will have to hack the game.

Input

The first line contains two space-separated integers n and m (1≤n,m≤20).

Next n lines contain m characters describing the playing field: the j-th character of the i-th line equals to the magical character of the corresponding field square.

Output

On the first line print "WIN" if Roma can win or "LOSE" if it is impossible to win considering that the opponent pays optimally.

Examples
Input
2 2
RL
LR
Output
LOSE
Input
2 2
RR
RR
Output
WIN
Note

In the first test each move makes one diagonal line of the square inactive, thus it is guaranteed that Roma loses after two moves.

There are three variants of making a move in the second test: to "finish off" the main diagonal line or any of the squares that are left. That means that after three moves the game stops and Roma wins.

Source/Category

 
[Submit] [Status]