Description

Little AA and Little YY got a movie ticket for "Pleasant Goat and Big Big Wolf". They both want to watch it, but there is only one ticket, so they decide the winner by playing a strategy game. The winner gets the ticket.

In an $N \times M$ maze there is a piece. Little AA first chooses any starting cell to place the piece. Then Little YY and Little AA take turns moving the piece to an adjacent cell. The rules state that in a single game, the same cell cannot be visited twice, and the piece cannot be moved into certain cells. When a player can no longer move the piece, the game ends, and the player who made the last move wins.

For example, in the maze below, . indicates a passable cell for the piece, and # indicates an impassable cell:

                                 .##
                                 ...
                                 #.# 

If Little AA places the piece at $(1, 1)$, then AA cannot win no matter what.

If Little AA places the piece at $(3, 2)$ or $(2, 3)$, then AA can win. For example, if AA places the piece at $(3, 2)$, Little YY can only move it to $(2, 2)$. Then AA moves the piece to $(2, 3)$ and wins the game.

Little AA and Little YY are both extremely smart and never make mistakes. Can Little AA win this game and get the precious movie ticket?

Input Format

The input begins with two integers $N, M$, representing the dimensions of the maze.

Then follow $N$ lines, each with $M$ characters describing the maze.

Output Format

If Little AA can win the game, output a line WIN, then output all winning starting positions in row-major order, one per line. For each line, print the position as two integers $r$ and $c$ (1-based).

Otherwise, output a single line LOSE.

3 3
.##
...
#.#

WIN
2 3
3 2

Hint

Constraints:

• For $30\%$ of the testdata, $N, M \leq 5$.
• For $100\%$ of the testdata, $1 \leq N, M \leq 100$.

Translated by ChatGPT 5