Duel

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.

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.

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.