VCF

오목은 흑돌과 백돌이 번갈아 오목판에 돌을 두어 한 줄에 같은 색깔의 돌을 가로, 세로, 또는 대각선으로 정확히 5개 연결한 형태인 오목을 먼저 완성한 사람이 승리하는 게임이다. 오목에는 VCF (Victory by Continuous Fours)라는 공격 형태가 있는데, 이는 사목을 연속으로 만든 뒤, 최종적으로 오목을 두어서 승리하는 것을 의미한다. 여기서 사목이란 다섯 칸의 범위 내에 같은 색의 돌이 4개 있고, 돌 하나를 더 붙여서 오목을 완성할 수 있는 자리가 한 군데 또는 두 군데 존재하는 모양을 의미한다.

아티초크는 기보 데이터가 주어졌을 때, 주어진 색의 플레이어에게 VCF가 존재하여 3수 이내에 오목을 완성할 수 있는지 여부를 판별하는 프로그램을 짜려고 했지만, 구현 능력이 부족하여 당신에게 도움을 요청했다. 아티초크를 위해 프로그램을 대신 작성해 보자.

처음 $15$줄에는 $15$개의 알파벳으로 기보 데이터, 즉 오목판의 상태가 주어진다. 검은 오목알이 놓인 자리는 B, 흰 오목알이 놓인 자리는 W, 오목알이 놓이지 않은 자리는 X로 표시되며, 각 알파벳은 붙어서 입력으로 주어진다. 이때, 주어진 오목판에는 오목이 존재하지 않음이 보장되며, 오목판의 초기 상태에 W와 B의 개수의 합은 200을 넘지 않는다.

$16$번째 줄에는 B 또는 W가 주어진다. B가 주어진 경우 플레이어는 흑돌이고, W가 주어진 경우 플레이어는 백돌이다.

주어진 오목판에서 플레이어의 차례일 때, 플레이어에게 VCF가 존재하지 않거나, 3수 이내에 오목을 완성할 수 없는 경우 -1을 출력하고 프로그램을 종료한다.

플레이어에게 VCF가 존재하여 3수 이내에 오목을 완성할 수 있는 경우, 다음 쿼리를 최대 3번까지 사용할 수 있다.

• $x_p$ $y_p$: $x_p$행 $y_p$열 $(1 \leq x_p, y_p \leq 15)$에 플레이어가 돌을 놓는다.
  • 단, 지정한 위치에 이미 돌이 놓여 있거나, 돌을 두었을 때 사목 또는 오목이 완성되지 않으면 를 받는다.

채점 시스템에 쿼리를 출력했을 때, 플레이어가 오목을 완성했다면, 를 받는다.

오목을 완성하지 못한 상태라면, 채점 시스템이 다음과 같은 방식으로 상대방의 다음 수를 반환한다.

• $x_o$ $y_o$: $x_o$행 $y_o$열 $(1 \leq x_o, y_o \leq 15)$에 상대방이 돌을 놓는다.

  • 상대방에게 오목을 완성할 수 있는 자리가 있는 경우 해당 자리를 우선적으로 두며, 이 경우 를 받는다.
  • 그렇지 않은 경우, 상대방은 플레이어가 다음 차례에 오목을 완성할 수 있는 자리에 돌을 둔다.
  • 플레이어가 다음 차례에 오목을 완성할 수 있는 자리가 여러 곳인 경우, 채점 시스템은 그 중 한 자리를 랜덤으로 골라서 둔다.

금수는 고려하지 않는다.