Renju

문제

$15 \times 15$ 크기의 보드 위에서 두 플레이어가 오목 게임을 진행합니다.

보드는 $1$행 $1$열부터 $15$행 $15$열까지 $225$개의 칸으로 구성되며, $x$행 $y$열의 칸을 $(x, y)$로 표기합니다.

각 칸은 빈 칸 .과 선, 후공 플레이어의 돌 B, W 중 하나의 상태를 가집니다. 초기에는 다음과 같이 돌이 배치됩니다.

---

게임은 선공 플레이어부터 시작해 두 플레이어가 번갈아 턴을 진행합니다.

• 플레이어는 자신의 턴에 빈 칸 $(x, y)$를 골라 자신의 돌을 놓거나, PASS를 선택할 수 있습니다.
• 첫 번째 턴에 선공 플레이어는 PASS를 선택할 수 없으며, $(8, 8)$에 돌을 놓아야 합니다.
• 두 번째 턴에 후공 플레이어는 PASS를 선택할 수 없으며, $(x, y) (7 \le x, y \le 9)$에 돌을 놓아야 합니다.
• 세 번째 턴에 선공 플레이어는 PASS를 선택할 수 없으며, $(x, y) (6 \le x, y \le 10)$에 돌을 놓아야 합니다.

위의 그림은 선공 플레이어가 $(10, 8)$에 돌을 놓는 예시입니다.

1. TERMS AND DEFINITIONS

렌주 규칙(Renju)을 구성하는 핵심 용어들은 다음과 같이 정의합니다.

1. ROW: 대각선, 수직, 수평선상에 연속해 놓인 빈 칸과 돌의 조합을 의미합니다. ROW 내부에는 적어도 하나 이상의 돌이 있어야 하며, ROW 내부의 돌은 모두 B이거나 모두 W여야 합니다. ROW의 양 끝은 보드의 가장자리, 다른 색상 돌 또는 빈 칸으로 막혀있어야 합니다.

• A와 B는 ROW입니다.
• C는 양 끝 중 하나가 같은 색상 돌이기 때문에 ROW가 아닙니다.

2. UNBROKEN ROW: 내부에 빈 칸이 없는 ROW를 의미합니다.

• B는 내부에 빈 칸이 있기 때문에 UNBROKEN ROW가 아닙니다.
• D는 UNBROKEN ROW입니다.

3. FIVE IN A ROW: $5$개의 돌로 이루어진 UNBROKEN ROW를 의미합니다.

• E는 FIVE IN A ROW입니다.

4. OVERLINE: $6$개 이상의 돌로 이루어진 UNBROKEN ROW를 의미합니다.

• F는 $6$개의 돌로 이루어진 OVERLINE입니다.

5. FOUR: $4$개의 돌로 이루어진 ROW 중, 하나의 돌을 더 놓아서 FIVE IN A ROW를 만들 수 있는 ROW를 의미합니다.

• G와 H는 하나의 돌을 더 놓아서 FIVE IN A ROW를 만들 수 있기 때문에 FOUR입니다.

6. STRAIGHT FOUR: $4$개의 돌로 이루어진 UNBROKEN ROW 중, 하나의 돌을 더 놓아서 FIVE IN A ROW를 만드는 방법이 $2$가지인 UNBROKEN ROW를 의미합니다.

• H는 하나의 돌을 더 놓아서 FIVE IN A ROW를 만드는 방법이 $2$가지이기 때문에 STRAIGHT FOUR입니다.
• G는 하나의 돌을 더 놓아서 FIVE IN A ROW를 만드는 방법이 $1$가지이기 때문에 STRAIGHT FOUR가 아닙니다.

7. THREE: $3$개의 돌로 이루어진 ROW 중, 하나의 돌을 더 놓아서 FIVE IN A ROW를 만들지 않는 동시에 STRAIGHT FOUR를 만들 수 있는 ROW를 의미합니다.

• I와 J는 하나의 돌을 더 놓아서 FIVE IN A ROW를 만들지 않으면서 STRAIGHT FOUR를 만들 수 있기 때문에 THREE입니다.
• K, L, M은 하나의 돌을 더 놓아서 STRAIGHT FOUR를 만들 수 없기 때문에 THREE가 아닙니다.
• N은 하나의 돌을 더 놓아서 STRAIGHT FOUR를 만들 수는 있지만, 동시에 FIVE IN A ROW가 만들어지기 때문에 THREE가 아닙니다.

8. DOUBLE FOUR: 빈 칸에 돌을 놓아 해당 칸을 포함하는 서로 다른 FOUR가 $2$개 이상 만들어지는 것을 의미합니다.

• O는 서로 다른 FOUR가 $2$개 이상 만들어지기 때문에 DOUBLE FOUR입니다.

9. DOUBLE THREE: 빈 칸에 돌을 놓아 해당 칸을 포함하는 서로 다른 THREE가 $2$개 이상 만들어지는 것을 의미합니다.

• P는 THREE가 하나 만들어지기 때문에 DOUBLE THREE가 아닙니다.
• Q는 서로 다른 THREE가 $2$개 이상 만들어지기 때문에 DOUBLE THREE입니다.

2. FORBIDDEN MOVES

렌주 규칙(Renju)은 선공 플레이어와 후공 플레이어의 유불리를 줄이기 위해 선공 플레이어에게 다음의 추가 규칙을 적용합니다.

1. 선공 플레이어는 동시에 FIVE IN A ROW를 만들지 않는 이상 OVERLINE, DOUBLE FOUR, DOUBLE THREE를 만들 수 없습니다.

• A는 DOUBLE FOUR이기 때문에 선공 플레이어가 둘 수 없습니다.

• B는 OVERLINE이기 때문에 선공 플레이어가 둘 수 없습니다.

• C는 DOUBLE FOUR이지만, 동시에 FIVE IN A ROW가 만들어지기 때문에 선공 플레이어가 둘 수 있습니다.

• D와 E는 DOUBLE THREE이기 때문에 선공 플레이어가 둘 수 없습니다.

• F, H와 I는 DOUBLE THREE이기 때문에 선공 플레이어가 둘 수 없습니다.

• G는 DOUBLE FOUR이기 때문에 선공 플레이어가 둘 수 없습니다.

2. 단, 흑의 DOUBLE THREE는 렌주 규칙(Renju) 9.3조에 의해 만들어진 THREE 중 STRAIGHT FOUR로 만들기 위해 돌을 추가해야 하는 칸이 OVERLINE이나 DOUBLE FOUR가 되는 칸이라 결과적으로 유효한 THREE가 $1$개 이하가 될 때 허용됩니다. 또한 STRAIGHT FOUR로 만들기 위해 돌을 추가해야 하는 칸이 또 다른 금지된 DOUBLE THREE가 되는 칸이라 유효한 THREE가 $1$개 이하가 되는 경우에도 허용됩니다. 또 다른 DOUBLE THREE가 허용되는지 확인하려면 먼저 앞선 기준에 따라 허용되는지 검토한 뒤 STRAIGHT FOUR를 만드는 시뮬레이션을 계속하여 연쇄적으로 발생하는 다른 DOUBLE THREE까지 동일한 방식으로 판별해야 합니다.

• J는 가로 방향으로 만들어지는 THREE를 STRAIGHT FOUR로 만들기 위해 돌을 추가해야 하는 칸이 OVERLINE이 되는 칸이라 유효한 THREE가 $1$개이기 때문에 선공 플레이어가 둘 수 있습니다.
• K는 오른쪽 아래 대각선 방향으로 만들어지는 THREE를 STRAIGHT FOUR로 만들기 위해 돌을 추가해야 하는 칸이 DOUBLE FOUR가 되는 칸이라 유효한 THREE가 $1$개이기 때문에 선공 플레이어가 둘 수 있습니다.
• L은 가로 방향으로 만들어지는 THREE를 STRAIGHT FOUR로 만들기 위해 돌을 추가해야 하는 칸이 허용되지 않는 DOUBLE THREE가 되는 칸이라 유효한 THREE가 $1$개이기 때문에 선공 플레이어가 둘 수 있습니다.

3. WIN OF A GAME

게임은 다음 조건 중 하나가 만족될 때 종료됩니다.

• 선공 플레이어가 FIVE IN A ROW를 만들었다면 선공 플레이어가 승리합니다.

• 후공 플레이어가 FIVE IN A ROW 또는 OVERLINE을 만들었다면 후공 플레이어가 승리합니다.

• 두 플레이어가 연속해서 PASS를 선택했다면 무승부로 종료됩니다.

보드의 최종 승자가 되기 위한 AI를 설계해주세요!

NOTE.

렌주 규칙(Renju)은 선공 플레이어와 후공 플레이어의 유불리를 더 줄이기 위해 12.1~12.9조의 오프닝 규칙을 추가로 적용하지만, 본 문제에서는 구현의 편의를 위해 의도적으로 오프닝 규칙을 생략했습니다.

입력

채점기는 다음의 한 줄 단위로 플레이어와 통신합니다.

• x, y는 정수입니다.
• my_time, opp_time, time은 정수이며, 시간은 밀리초(millisecond) 단위로 주어집니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다.
• 시간 제한이 있는 명령에서 출력을 제한 내에 수행하지 않으면 시간 초과(TLE) 판정을 받습니다.
• 출력 형식에 맞지 않는 문자열을 출력하거나, TURN 명령어가 주어질 때 합법적이지 않은 수를 출력하면 런타임 에러(RE) 판정을 받습니다.

예시