D. World of Darkraft

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

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.

Оролт

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.

Гаралт

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

Орчуулсан: [орчуулагдаж байгаа]

Жишээ тэстүүд

Оролт
2 2
RL
LR
Гаралт
LOSE
Оролт
2 2
RR
RR
Гаралт
WIN

Тэмдэглэл

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.

Сэтгэгдлүүдийг ачааллаж байна...