Hide

Problem H
Nine Knights

In the game of chess, knights are unique due to their “L-shaped” movement. A knight can move, as shown in Figure 1, by either moving two squares sideways and one square up or down, or moving one square sideways and two squares either up or down.

\includegraphics[width=0.35\textwidth ]{moves.png}
Figure 1: The highlighted squares show all possible moves for a knight.

In the Nine Knights puzzle, exactly nine knights must be positioned on a 5-by-5 board so that no knight can attack another knight with a single move. The configuration shown in Figure 2 is an invalid solution because two of the knights can attack each other, where the configuration shown in Figure 3 is a valid solution.

\includegraphics[width=0.35\textwidth ]{invalid_nocolor.png}

Figure 2: Invalid game configuration

\includegraphics[width=0.35\textwidth ]{valid_nocolor.png}

Figure 3: Valid game configuration

Given the description of a game configuration, your job is to determine whether or not it represents a valid solution to the Nine Knights puzzle.

Input

The input will consist of $5$ lines, each having $5$ characters. All characters will be either ’k’, indicating the placement of a knight, or ’.’, indicating an empty space on the board.

Output

Display the word valid if the given chess board is a valid solution to the Nine Knights puzzle. Otherwise, display the word invalid.

Sample Input 1 Sample Output 1
...k.
...k.
k.k..
.k.k.
k.k.k
invalid
Sample Input 2 Sample Output 2
.....
...k.
k.k.k
.k.k.
k.k.k
valid
Sample Input 3 Sample Output 3
.....
...k.
k.k.k
.k.k.
k...k
invalid

Please log in to submit a solution to this problem

Log in