EIU Programming Practices and Exams

The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal.

Input

Input will contain a description of a single chess board, given as eight lines of eight characters each. Input lines will consist of only the characters ‘.’ and ‘*’. The ‘.’ character represents an empty space on the board, and the ‘*’ character represents a queen.

Output

Print a single line of output. Print the word “valid” if the given chess board is a valid solution to the eight queens problem. Otherwise, print “invalid”.

Example

Input:
*.......
..*.....
....*...
......*.
.*......
.......*
.....*..
...*....

Output:
invalid

Input:
*.......
......*.
....*...
.......*
.*......
...*....
.....*..
..*.....

Output:
valid