시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 7 6 6 85.714%

문제

In the game of chess, knights are unique due to their “L-shaped” movement. A knight can move, as shown in Figure A.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.

Figure A.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 A.2 is an invalid solution because two of the knights can attack each other, where the configuration shown in Figure A.3 is a valid solution.

Figure A.2: Invalid game configuration Figure A.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.

입력

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.

출력

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

예제 입력 1

...k.
...k.
k.k..
.k.k.
k.k.k

예제 출력 1

invalid

예제 입력 2

.....
...k.
k.k.k
.k.k.
k.k.k

예제 출력 2

valid

예제 입력 3

.....
...k.
k.k.k
.k.k.
k...k

예제 출력 3

invalid

힌트