Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. World of Darkraft

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRecently 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.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/07/2020 23:37:16 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|