1794: Tic Tac Toe

The game of Tic Tac Toe is played on an

-by-

grid (where

is usually but not necessarily three). Two players alternate placing symbols on squares of the grid. One player places Xes and the other player places Os. The player placing Xes always goes first. When the grid contains a vertical, horizontal, or diagonal sequence of at least

consecutive squares all containing the same symbol, the game ends and the winner is the player who placed the last symbol. When all the squares of the grid are filled, if neither player has won, the game ends in a draw.

Your task is to analyze the state of a Tic Tac Toe board, and determine whether the game is still in progress, or if it has completed, who won, or if the game ended in a draw. You should also detect erroneous states of the Tic Tac Toe board that could never occur during an actual game.

The first line of input contains the two integers n and m, separated by spaces, with 1 <= m <= n <= 2000. The following n lines of input each contain one row of the Tic Tac Toe board. Each of these lines contains exactly n characters, and each of these characters is either an X, an O, or a period (.), indicating an empty square.

Output a single line containing the appropriate string X WINS, O WINS, or DRAW if the game is over, the string IN PROGRESS if the game has not yet finished, or ERROR if the state of the board could never occur during a game.

3 3
..X
OOX
..X

X WINS