Nine Knights

In chess, a knight moves in an L shape. As Figure A.1 shows, it moves two squares sideways and then one square up or down, or one square sideways and then two squares up or down.

Figure A.1: The highlighted squares are every square the knight can reach in one move.

In the Nine Knights puzzle you place exactly nine knights on a $5 \times 5$ board so that no knight can attack another knight in a single move. The configuration in Figure A.2 is not a solution because two of the knights attack each other. The configuration in Figure A.3 is a solution.

Figure A.2: An invalid configuration	Figure A.3: A valid configuration

Given one configuration, decide whether it is a valid solution to the Nine Knights puzzle.

The input consists of 5 lines of 5 characters each. Every character is either k, meaning a knight stands on that square, or a period, meaning the square is empty.

Print valid if the given board is a valid solution to the Nine Knights puzzle. Otherwise print invalid.