얼티밋 틱택토

틱택토는 두 사람이 하는 아주 간단한 게임이다. 3행 3열의 빈 판에서 시작한다. 첫 번째 플레이어가 칸 하나를 골라 자기 기호 X를 적고, 두 번째 플레이어가 남은 빈 칸 하나를 골라 자기 기호 O를 적는다. 세 번째 차례에는 다시 첫 번째 플레이어가 빈 칸을 고른다. 이렇게 번갈아 두며 차례를 건너뛸 수 없다. 같은 행, 같은 열, 두 대각선 중 어느 한 곳에 자기 기호를 세 개 놓은 플레이어가 이긴다. 아무도 이기지 못한 채 판이 다 차면 무승부다.

엘리와 크리스는 규칙을 바꿔서 논다. $3 \times 3$ 판 대신 무한히 큰 빈 판에서 시작한다. 첫 수는 어디에 두어도 된다. 그다음부터는 이미 놓인 돌 전부와 새로 놓는 돌이 함께 어떤 $3 \times 3$ 정사각형 안에 들어가도록 빈 칸을 골라야 한다. 그래서 두 번째 수는 첫 수에서 행으로도 열로도 2칸을 넘지 못한다. 게임이 진행될수록 둘 수 있는 칸의 범위는 좁아지고, 아무도 그전에 이기지 않으면 결국 보통의 $3 \times 3$ 판이 된다.

승리 조건은 원래 게임과 같다. 같은 행, 같은 열, 대각선에서 이웃한 세 칸을 먼저 차지한 플레이어가 이긴다. 아무도 이기지 못한 채 둘 수 있는 칸이 모두 차면 무승부다.

진행 예시는 다음과 같다. 점은 빈 칸이다.

X가 첫 수를 둔다. 판은 무한하지만 이제 둘 수 있는 칸은 5행 5열로 정해진다.

.....
.....
..X..
.....
.....

O가 맨 아랫줄에 둔다.

.....
.....
..X..
.....
..O..

두 돌이 세 행에 걸쳐 있으므로 범위가 3행 5열로 줄어든다. X가 한 칸 오른쪽에 둔다.

..XX.
.....
..O..

돌이 두 열에 걸쳐 있으므로 범위가 3행 4열로 줄어든다.

.XX.
....
.O..

O가 오른쪽 끝에 둔다.

.XXO
....
.O..

이제 범위가 3행 3열이 되고, X가 가운데에 둔다.

XXO
.X.
O..

O가 오른쪽 아래에 둔다.

XXO
.X.
O.O

X가 가운데 열을 채워서 이긴다.

XXO
.X.
OXO

이 예시에서는 X가 이겼지만, O가 더 잘 두었다면 그렇지 않았다.

최적의 수는 이렇게 정의한다. 이길 수 있으면 이기는 수, 이길 수는 없지만 비길 수 있으면 비기는 수, 둘 다 불가능하면 지는 수를 고른다. 상대도 최적으로 둔다고 가정한다.

판의 현재 상태가 주어지면, 이번에 둘 플레이어가 최적으로 둘 때 고르는 칸을 구하는 프로그램을 작성하라.

첫 줄에 남아 있는 유효한 행의 수 $N$과 열의 수 $M$이 공백을 두고 주어진다. 이어지는 $N$개 줄에는 길이가 $M$인 문자열이 하나씩 주어지고, 각각 판의 한 행을 위에서부터 나타낸다. 입력은 항상 올바른 판의 상태다. 이미 적어도 한 수가 놓여 있어서 둘 수 있는 칸이 유한하고, 게임은 아직 끝나지 않았다.

첫째 줄에 두 정수 $R$과 $C$를 공백을 두고 출력한다. 이번에 둘 플레이어가 최적으로 둘 때 고르는 칸의 행 번호와 열 번호이며, 둘 다 1부터 센다. 최적인 칸이 여럿이면 사전순으로 가장 앞선 칸을 출력한다. 즉 $R$이 가장 작은 칸을 고르고, 그런 칸이 여럿이면 그중 $C$가 가장 작은 칸을 고른다.

• $3 \le N, M \le 5$
• 판을 나타내는 문자는 '.'(점), 'X'(대문자), 'O'(대문자) 세 가지다.
• X가 먼저 두므로 판에 놓인 X의 개수는 O의 개수와 같거나 하나 더 많다.

다음 상태에서는 O의 차례다.

.XX.
....
.O..

O가 (1, 4)에 두면 남은 범위가 2열부터 4열까지인 $3 \times 3$ 판으로 줄어든다. 이때 X가 원래 판의 (2, 3)에 두면 O는 이중 위협에 걸린다. O가 어느 칸을 막아도 X에게 이기는 수가 남는다.

O가 (1, 1)에 두면 남은 범위가 1열부터 3열까지로 줄어들어서, X가 (1, 4)에 두어 한 번에 이기는 길이 사라진다. 이 수부터는 O가 무승부로 이끄는 전략이 있다.