Mid-Central USA Programming Contest 2017

Start

2017-11-04 17:30 UTC

Mid-Central USA Programming Contest 2017

End

2017-11-04 22:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -407 days 1:22:57

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
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