Tic-Tac-Toe

Tic-tac-toe is a game in which two players alternately place marks on a 3×3 grid that starts out empty. The first player always places X and the second player always places O, taking turns one mark at a time.

At any moment, if one player's marks fill an entire line of three cells horizontally, vertically, or diagonally, that player wins and the game ends immediately. If all nine cells are filled without either player completing a line, the game ends in a draw.

Given a single board state, decide whether it is a state in which a real game of tic-tac-toe played by the rules above could have ended.

The input consists of several test cases. Each test case is a single line of nine characters, where each character is one of X, O, or . (a dot denotes an empty cell). The nine characters list the board from the top row to the bottom row, left to right within each row. The last line of the input is the string end, which is not processed.

For each test case, print a single line: valid if the state could be the ending state of a real game, or invalid otherwise.