COCI 2006/2007, Contest #6

Task MARATON

Albert, Barbara, Casper, Dinko, Eustahije are starting a marathon game of tic-tac-toe, played on an N×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 3 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.

Input

The first line of input contains the integer N (1 ≤ N ≤ 30), 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.

Output

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

Sample Tests

Input

3
XOC
XOC
X..

Output

X

Input

4
....
..A.
AAB.
.B.B

Output

ongoing

Input

3
ABB
AAA
BBA

Output

A

All Submissions
Best Solutions


Point Value: 5
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 14, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3