Duel

Time limit2sMemory limit128 MB

Summary

Two players alternately mark empty cells on a strip, winning instantly by forming three consecutive marks, and the task is to decide if the first player can force a win and list all winning first moves.

Level: Hard8 of 10
Topics: Game theory, Combinatorics, Dynamic programming, String
Solved: No attempts yet

Problem

Two players are dueling on a one-dimensional board of length N. Some cells are empty, and some cells already contain a P mark. The players alternate turns; on each turn, the player chooses one empty cell and marks it with P. A player wins immediately if their move creates three or more consecutive P marks.

It is currently the monkey's turn. Both the monkey and the opponent play optimally. Given the current board, determine whether the monkey can force a win. If so, find every board position that can be chosen as the monkey's first move in a winning strategy.

Input

The first line contains the board size N. N is an integer between 3 and 3000, inclusive.

The second line contains a string of length N describing the current board. An empty cell is written as ., and an already marked cell is written as P.

Output

Print WINNING on the first line if the monkey can force a win; otherwise print LOSING.

If the answer is WINNING, print on the second line every 1-indexed position where the monkey can place P on the current turn and still force a win. Print the positions in increasing order, separated by spaces.

If the answer is LOSING, do not print a second line.

Examples3

Example 1
Input
```
8
.P.P..PP
```
Expected output
```
WINNING
3 6
```
Example 2
Input
```
3
.P.
```
Expected output
```
LOSING
```
Example 3
Input
```
8
.......P
```
Expected output
```
WINNING
3
```