Problem J
Game Night Feud

Source: Pixabay

Einstein’s School of Engineers (ESE) are known to be very competitive when it comes to sports. However, it doesn’t stop there, it turns out that they are very competitive when it comes to board games as well. In order to “up the ante,“ all of the students at ESE have decided to play Tic-Tac-Toe in groups of two while being blindfolded and have a third person (the referee) review the board and tell them who’s the winner. Because of the blindfolds, players may sometimes play out of turn, miss turns, or continue playing after one player has already won. The referee must announce a winner if there is one, declare the game a draw, announce that the board is invalid, or declare that the game is still in progress.

Write a program to assist the referee in determining the current status of a Tic-Tac-Toe game.

As a reminder, here are the rules of Tic-Tac-Toe when it is played normally: Players take turns filling their symbol into an empty square, with one player representing crosses and the other circles. The first player to mark three of their symbols along a row, column, or diagonal wins, which ends the game. If the board is filled without any player achieving a win the game is a tie.

Input

The input consists of $4$ lines. The first line contains two strings consisting of up to $10$ English upper or lowercase letters each, which are the names of the players. The first player listed will use crosses (and makes the first move) and the second player will use circles. The following $3$ lines each represent a row of the Tic-Tac-Toe board. Each line consists of $3$ characters, and the possible characters are ‘X‘, ‘O‘, and ‘_‘.

Output

If a winner is determined, output their name. If the game has ended in a draw, output “Draw”. If the provided Tic-Tac-Toe board is invalid, output “Invalid Game”. If the game is still in progress, output “In-Progress”. Your program should base its output on the current position only, not projecting future positions. In particular, positions that have trapped a player such that they will lose under perfect play by the other side still count as “In-Progress”.

Liam Noah
X_O
X_O
X_O

Invalid Game

Mark Taylor
OXO
OXX
XOX

Draw

Jim James
XOX
OXO
OXX

Jim

Jamie Ben
XOX
_OX
___

In-Progress