시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB349564722.927%

문제

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 자기의 영원한 숙적인 멍멍이를 만나게 되었다. 외나무다리에서 만난 그들... 이제 둘의 피할 수 없는 결투가 펼쳐진다!!

원숭이와 멍멍이의 결투는 N칸의 게임보드에서 펼쳐진다. 처음에 N칸의 보드에는 아무것도 없다. 그리고는 둘이 번갈아가면서 각 칸에 뷁표시를 한 번씩 한다. 그러다가 연속해서 3개 이상 뷁표시를 만드는 사람이 이기게 되는 게임이다.

원숭이와 멍멍이가 처음 상태에서 어느 정도 게임을 진행하였다. 그러다 원숭이는 도저히 전략을 세울 수 없어서 여러분에게 도움을 요청하였다. 현재 원숭이차례인 게임보드의 상태가 주어졌을 때, 원숭이가 이길 수 있는지, 이길 수 있다면 이기는 방법을 구하는 프로그램을 작성하시오. 원숭이와 멍멍이는 각자 최선을 다해 결투를 벌인다.

입력

첫째 줄에 게임보드의 크기 N이 주어진다. N은 3이상 3,000이하인 자연수이다. 그 다음 줄에 현재 게임보드의 상태가 주어진다. 빈칸은 ‘.’, 뷁표시는 ‘P’로 주어진다.

출력

첫째 줄에 원숭이의 승패를 출력한다. 이길 수 있다면 “WINNING"을, 이길 수 없다면 "LOSING"을 출력한다. 이길 수 있다면 그 다음 줄에 이기는 방법을 출력한다. 원숭이가 현재 차례에 뷁표시를 놓아서 이길 수 있는 곳을 오름차순으로 출력한다. 이길 수 없다면 출력하지 않는다.

예제 입력 1

8
.P.P..PP

예제 출력 1

WINNING
3 6

예제 입력 2

3
.P.

예제 출력 2

LOSING

예제 입력 3

8
.......P

예제 출력 3

WINNING
3

출처