푸세

Pousse(프랑스어로 "밀다"라는 뜻)는 $N \times N$ 크기의 판에서 두 사람이 하는 게임이다. 두 참가자 $X$와 $O$는 번갈아 가며 자기 색의 말을 하나씩 놓으며, 항상 $X$가 먼저 시작한다. 처음에 판은 비어 있다. 행과 열은 왼쪽 위 모서리를 기준으로 $1$부터 $N$까지 번호가 매겨진다.

   1 2 3 4
  +-+-+-+-+
1 | | | | |
  +-+-+-+-+
2 | | | | |
  +-+-+-+-+
3 | | | | |
  +-+-+-+-+
4 | | | | |
  +-+-+-+-+

말은 어떤 행의 왼쪽이나 오른쪽에서, 또는 어떤 열의 위나 아래에서 밀어 넣는 방식으로만 놓을 수 있다. 따라서 가능한 이동은 모두 $4N$가지이며, 각각 Li, Ri, Ti, Bi로 나타낸다. 이는 각각 행 또는 열 i에 대해 왼쪽(Left), 오른쪽(Right), 위쪽(Top), 아래쪽(Bottom)에서 말을 넣는다는 뜻이다.

말이 들어가는 칸은 그 행이나 열의 끝 칸이다(Li이면 $1$열, Ri이면 $N$열, Ti이면 $1$행, Bi이면 $N$행). 그 칸이 비어 있으면 말은 그대로 그 칸에 놓인다. 비어 있지 않다면, 그 끝 칸에서부터 그 행이나 열의 첫 번째 빈 칸에 이르기까지의 모든 말이 한 칸씩 더 밀려나 자리를 만들고, 새 말이 그 끝 칸을 차지한다. 만약 그 행이나 열에 빈 칸이 하나도 없다면, 반대쪽 끝에 있는 말이 판 밖으로 밀려나 제거된다.

어떤 행이나 열의 $N$개 칸이 모두 같은 색의 말로 채워지면, 그 행 또는 열을 그 색의 스트레이트(straight)라고 한다. 매 이동 후 각 색의 스트레이트 개수를 센다. 어떤 이동의 결과로 한 색의 스트레이트 개수가 다른 색보다 많아지는 순간 게임이 끝나고, 그 색의 참가자가 이긴다.

첫째 줄에 정수 $N$($1 \le N \le 100$)이 주어진다. 그다음 줄부터는 위에서 설명한 표기법에 따라 한 줄에 하나씩 이동이 주어지며, 여분의 공백이나 빈 줄은 없다. 주어지는 모든 이동은 유효하다. 입력의 마지막 줄은 항상 QUIT이다.

이동을 순서대로 진행한다. 어떤 이동의 결과로 한 색의 스트레이트 개수가 다른 색보다 많아지면, 그 즉시 우세한 색에 따라 X WINS 또는 O WINS를 출력하고 멈춘다. 승자가 정해지기 전에 QUIT 줄에 도달하면 TIE GAME을 출력한다.