Tic-Tac-Toe

Time limit1sMemory limit128 MB

Summary

Given a final tic-tac-toe board, decide whether it could result from a legal game played by the rules.

Level: Medium5 of 10
Topics: Implementation, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1

Input

XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end

Expected output

invalid
valid
invalid
valid
valid
invalid
invalid
invalid

Example 2
Input
```
XOXXOOOXX
end
```
Expected output
```
valid
```
Example 3
Input
```
XXXOO....
end
```
Expected output
```
valid
```