시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB123538331632.410%

문제

상근(Albert), 민혁(Barbara), 선영(Casper), 창영(Dinko), 현진(Eustahije)이가 마라톤 틱택토 게임을 하려고 한다. 이 게임은 N×N 보드에서 진행한다.

맨 처음에 보드의 모든 칸은 비어있다. 플레이어는 턴을 번갈아가면서 자신의 영어 이름의 첫 글자를 빈 칸에 적는다. (두 사람의 영어 이름의 첫 글자가 같은 경우는 없다)

게임은 세 글자가 행, 열, 또는 대각선으로 연속할 때, 그 플레이어가 승리하며, 게임이 끝나게 된다.

보드판의 상태가 주어졌을 때, 게임이 끝났는지 아닌지를 결정하고, 끝났다면 승자가 누구인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드판의 크기 N이 주어진다. (1 ≤ N ≤ 30)

다음 N개 줄에는 보드판의 상태가 주어진다. '.'는 빈 칸을 나타낸다.

항상 승리한 사람이 많아야 한 명인 경우만 입력으로 주어진다. 

출력

첫째 줄에 게임이 끝났다면, 승리한 사람의 영어 이름의 첫 글자를 출력한다. 그렇지 않다면, "ongoing"을 출력한다. 게임을 승리한 사람이 없는데, 빈 칸이 없는 경우에도 ongoing을 출력해야 한다.

예제 입력 1

3
XOC
XOC
X..

예제 출력 1

X

예제 입력 2

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

예제 출력 2

ongoing

예제 입력 3

3
ABB
AAA
BBA

예제 출력 3

A
W3sicHJvYmxlbV9pZCI6IjMwMjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWI3N2NcdWQxYTQgXHVkMmYxXHVkMGRkXHVkMWEwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmMoQWxiZXJ0KSwgXHViYmZjXHVkNjAxKEJhcmJhcmEpLCBcdWMxMjBcdWM2MDEoQ2FzcGVyKSwgXHVjYzNkXHVjNjAxKERpbmtvKSwgXHVkNjA0XHVjOWM0KEV1c3RhaGlqZSlcdWM3NzRcdWFjMDAgXHViOWM4XHViNzdjXHVkMWE0IFx1ZDJmMVx1ZDBkZFx1ZDFhMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBOJnRpbWVzO04gXHViY2Y0XHViNGRjXHVjNWQwXHVjMTFjIFx1YzljNFx1ZDU4OVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU4IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJjZjRcdWI0ZGNcdWM3NTggXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWQxMzRcdWM3NDQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1Yzc5MFx1YzJlMFx1Yzc1OCBcdWM2MDFcdWM1YjQgXHVjNzc0XHViOTg0XHVjNzU4IFx1Y2NhYiBcdWFlMDBcdWM3OTBcdWI5N2MgXHViZTQ4IFx1Y2U3OFx1YzVkMCBcdWM4MDFcdWIyOTRcdWIyZTQuIChcdWI0NTAgXHVjMGFjXHViNzhjXHVjNzU4IFx1YzYwMVx1YzViNCBcdWM3NzRcdWI5ODRcdWM3NTggXHVjY2FiIFx1YWUwMFx1Yzc5MFx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1YzEzOCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVkNTg5LCBcdWM1ZjQsIFx1YjYxMFx1YjI5NCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNWYwXHVjMThkXHVkNTYwIFx1YjU0YywgXHVhZGY4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWMyYjlcdWI5YWNcdWQ1NThcdWJhNzAsIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjZjRcdWI0ZGNcdWQzMTBcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwYWNcdWIyOTRcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwXHViOTdjIFx1YWNiMFx1YzgxNVx1ZDU1OFx1YWNlMCwgXHViMDVkXHViMGFjXHViMmU0XHViYTc0IFx1YzJiOVx1Yzc5MFx1YWMwMCBcdWIyMDRcdWFkNmNcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmNmNFx1YjRkY1x1ZDMxMFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDMwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViY2Y0XHViNGRjXHVkMzEwXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7LiYjMzk7XHViMjk0IFx1YmU0OCBcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NmRcdWMwYzEgXHVjMmI5XHViOWFjXHVkNTVjIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWI5Y2VcdWM1NDRcdWM1N2MgXHVkNTVjIFx1YmE4NVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwYWNcdWIyZTRcdWJhNzQsIFx1YzJiOVx1YjlhY1x1ZDU1YyBcdWMwYWNcdWI3OGNcdWM3NTggXHVjNjAxXHVjNWI0IFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWNjYWIgXHVhZTAwXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCwgJnF1b3Q7b25nb2luZyZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyYjlcdWI5YWNcdWQ1NWMgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzVjNlx1YjI5NFx1YjM3MCwgXHViZTQ4IFx1Y2U3OFx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0IG9uZ29pbmdcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFSQVRPTiIsImRlc2NyaXB0aW9uIjoiPHA+QWxiZXJ0LCBCYXJiYXJhLCBDYXNwZXIsIERpbmtvLCBFdXN0YWhpamUgYXJlIHN0YXJ0aW5nIGEgbWFyYXRob24gZ2FtZSBvZiB0aWMtdGFjLXRvZSwgcGxheWVkIG9uIGFuIE4mdGltZXM7TiBib2FyZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW5pdGlhbGx5LCBhbGwgc3F1YXJlcyBvbiB0aGUgYm9hcmQgYXJlIGVtcHR5IGFuZCBwbGF5ZXJzIHRha2UgdHVybnMgd3JpdGluZyB0aGUgZmlyc3QgbGV0dGVyIG9mIHRoZWlyIG5hbWUgaW50byBhbnkgb2YgdGhlIGVtcHR5IHNxdWFyZXMgKGJlY2F1c2UgdGhlIHBsYXllcnMgYXJlIGVsaXRlLCBubyB0d28gcGxheWVycyBoYXZlIHRoZSBzYW1lIGZpcnN0IGxldHRlcikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIGVuZHMgd2hlbiBzb21lIHBsYXllciBwbGFjZXMgMyBvZiBoaXMgb3IgaGVyIGxldHRlcnMgY29uc2VjdXRpdmVseSBpbiBhIHJvdywgY29sdW1uIG9yIGRpYWdvbmFsbHkuIFRoYXQgcGxheWVyIGlzIGRlY2xhcmVkIHRoZSB3aW5uZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0LCBnaXZlbiB0aGUgc3RhdGUgb2YgdGhlIGJvYXJkLCBkZXRlcm1pbmVzIGlmIHRoZSBnYW1lIGlzIG92ZXIgYW5kIHdobyB3b24gaWYgaXQgaXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDMwKSwgdGhlIHNpemUgb2YgdGhlIGJvYXJkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbiBOIGNoYXJhY3RlcnMgZWFjaC4gVGhlIGNoYXJhY3RlcnMgd2lsbCBiZSB1cHBlcmNhc2UgbGV0dGVycyBvZiB0aGUgRW5nbGlzaCBhbHBoYWJldCBvciAmIzM5Oy4mIzM5OyAoaWYgdGhlIHNxdWFyZSBpcyBlbXB0eSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IHRoZXJlIGlzIGF0IG1vc3Qgb25lIHdpbm5lci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JZiB0aGUgZ2FtZSBpcyBvdmVyLCBvdXRwdXQgdGhlIGZpcnN0IGxldHRlciBvZiB0aGUgd2lubmVyJiMzOTtzIG5hbWUuIElmIG5vdCwgb3V0cHV0ICZxdW90O29uZ29pbmcmcXVvdDsgKGV2ZW4gaWYgdGhlIGJvYXJkIGlzIGZ1bGwpLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #6 3번