결투
시간 제한2초메모리 제한128 MB
두 선수가 번갈아 빈칸에 표시를 채우며 연속된 세 칸을 만들면 즉시 이기는 게임에서, 선공이 필승인지 판단하고 필승으로 이어지는 첫 수를 모두 구하는 문제입니다.
문제
길이 N인 일렬 게임판에서 두 플레이어가 결투를 한다. 처음에는 일부 칸이 비어 있고, 일부 칸에는 이미 P 표시가 놓여 있다. 두 플레이어는 번갈아 빈 칸 하나를 골라 P로 표시하며, 자신의 차례에 P가 세 개 이상 연속되게 만들면 즉시 이긴다.
현재는 원숭이의 차례이다. 원숭이와 상대는 모두 최선의 전략으로 플레이한다. 현재 게임판이 주어졌을 때, 원숭이가 승리를 강제할 수 있는지 판단하고, 가능하다면 첫 수로 둘 수 있는 모든 승리 위치를 구하시오.
입력
첫째 줄에 게임판의 크기 N이 주어진다. N은 3 이상 3000 이하인 자연수이다.
둘째 줄에는 현재 게임판의 상태를 나타내는 길이 N의 문자열이 주어진다. 빈 칸은 ., 이미 표시된 칸은 P로 주어진다.
출력
첫째 줄에 원숭이가 승리를 강제할 수 있으면 WINNING, 그렇지 않으면 LOSING을 출력한다.
WINNING인 경우 둘째 줄에 원숭이가 현재 차례에 P를 놓아 승리를 강제할 수 있는 모든 칸 번호를 오름차순으로 출력한다. 칸 번호는 왼쪽부터 1부터 시작하며, 여러 개이면 공백으로 구분한다.
LOSING인 경우 둘째 줄을 출력하지 않는다.