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 1

*.......
..*.....
....*...
......*.
.*......
.......*
.....*..
...*....

Example Output 1

invalid

Example Input 2

*.......
......*.
....*...
.......*
.*......
...*....
.....*..
..*.....

Example Output 2

valid