Albert, Barbara, Casper, Dinko, Eustahije are starting a marathon game of tic-tac-toe, played on an \(N \times N\) board.

Initially, all squares on the board are empty and players take turns writing the first letter of their name into any of the empty squares (because the players are elite, no two players have the same first letter). The game ends when some player places \(N\) of his or her letters consecutively in a row, column or diagonally. That player is declared the winner.

Write a program that, given the state of the board, determines if the game is over and who won if it is.

The first line of input contains the integer \(N\) (\(1 \le N \le 100\)), the size of the board.

The following \(N\) lines contain \(N\) characters each. The characters will be uppercase letters of the English alphabet or . (if the square is empty).

The input data will be such that there is at most one winner.

If the game is over, output the first letter of the winner's name. If not, output ongoing (even if the board is full).

riseoj 작성

출처 COCI 2006/2007 Contest 6