Ultimate Tic-Tac-Toe

Tic-tac-toe is a game for two people with very simple rules. It is played on an empty board with three rows and three columns. The first player picks a cell and writes her sign X in it. The second player then picks an empty cell and writes her sign O in it. On the third turn the first player picks an empty cell again. The players alternate and cannot skip a turn. A player who gets three of her signs in the same row, the same column, or one of the two diagonals wins. If the board fills up with nobody winning, the game is a draw.

Elly and Kris play a modified version. Instead of a $3 \times 3$ board they start on an infinitely large empty board. The first move may go anywhere. Every later move must go on an empty cell chosen so that all the stones already placed, together with the new one, still fit inside some $3 \times 3$ square. The second move is therefore at most 2 rows and at most 2 columns away from the first one. The further the game goes, the smaller the set of playable cells gets, and if nobody has won before that it finally becomes an ordinary $3 \times 3$ board.

The winning condition is the same as in the original game. The player who first takes three neighbouring cells in the same row, the same column, or along a diagonal wins. If every playable cell is filled and nobody has won, the game is a tie.

Here is one full game. A dot is an empty cell.

X makes the first move. The board is infinite, but the playable cells are now fixed to 5 rows and 5 columns.

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

O plays on the bottom row.

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

The two stones span three rows, so the region shrinks to 3 rows and 5 columns. X plays one cell to the right.

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

The stones now span two columns, so the region shrinks to 3 rows and 4 columns.

.XX.
....
.O..

O plays at the right end.

.XXO
....
.O..

The region is now 3 rows and 3 columns, and X plays in the middle.

XXO
.X.
O..

O plays at the bottom right.

XXO
.X.
O.O

X fills the middle column and wins.

XXO
.X.
OXO

X won in this example, but with better play from O that would not have happened.

Optimal play is defined like this: a player makes a winning move if the game can be won, a drawing move if it cannot be won but can be tied, and a losing move if neither is available. The opponent is assumed to play optimally as well.

Given the current state of the board, write a program that finds the cell the player to move would choose under optimal play.

The first line of standard input contains two integers $N$ and $M$, the number of remaining valid rows and columns, separated by a space. Each of the next $N$ lines contains one string of length $M$ describing a row of the board, from top to bottom. The input always describes a correct state. At least one move has already been made, so the set of playable cells is finite, and the game has not finished yet.

Print two integers $R$ and $C$ on one line, separated by a space: the row and the column of the cell the player to move should choose under optimal play, both counted from 1. If several cells are optimal, print the lexicographically smallest one. That is, pick the smallest $R$, and among the cells with that $R$ pick the smallest $C$.

• $3 \le N, M \le 5$
• The board is described with three characters only: '.' (a dot), 'X' (the capital letter), and 'O' (the capital letter).
• X moves first, so the number of X marks on the board is equal to the number of O marks or larger by one.

It is O's turn in the state below.

.XX.
....
.O..

If O plays at (1, 4), the region shrinks to the $3 \times 3$ board covering columns 2 to 4. X then plays at (2, 3) of the original board and puts O in a fork: whichever cell O blocks, X still has a winning move.

If O plays at (1, 1), the region shrinks to columns 1 to 3, which removes X's one move win at (1, 4). From that move on, O has a strategy that leads to a tie.