time limit per test: 0.25 sec. memory limit per test: 65536 KB
input: standard output: standard
Qc and He play the famous game of Tic-Tac-Toe. The game is played on a 3x3 board. Qc plays with X-s, He plays with 0-s. The players make moves in turn, Qc moves first. The object of the game is to get three of your marks in a row. If there is no empty square to put the mark to, the game ends in a draw. Given the position in a game and assuming that both Qc and He play perfectly, you have to detect who would win the game, or that the game would end in a draw. If the position given is illegal, that is, it cannot occur in the game, you must report so.
The input file contains one or more test cases. Each test case consists of four lines. Each of the first three lines contains three characters, these lines describe the position on the board. The fourth line of each test case is empty. The position on the board is specified using characters "X", "0" (zero), and "." (dot). The input file is terminated by the string containing the word "Qc" on a line by itself. You may assume that no position occurs in the input file more than once.
Print one statement for each test case. Refer to the sample output for exact statements.
..X .X0 ...
..X .0. XX0
X0X X0. 0X.
X0X X0X X0X
X0X 0X0 X0X
X wins. 0 wins. Game is a draw. Illegal position. X wins.
Anton Golubev, Petrazavodsk SU
Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
August 26, 2005
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov