나이트 아홉 개

체스에서 나이트는 L자로 움직인다. 그림 A.1처럼 옆으로 두 칸 간 뒤 위나 아래로 한 칸 가거나, 옆으로 한 칸 간 뒤 위나 아래로 두 칸 간다.

그림 A.1: 색칠한 칸은 나이트가 한 번에 갈 수 있는 자리를 모두 표시한 것이다.

나이트 아홉 개 퍼즐에서는 $5 \times 5$ 판 위에 나이트를 정확히 아홉 개 놓는다. 이때 어떤 나이트도 한 번의 이동으로 다른 나이트를 공격하면 안 된다. 그림 A.2의 배치는 두 나이트가 서로 공격하므로 올바른 해답이 아니고, 그림 A.3의 배치는 올바른 해답이다.

그림 A.2: 올바르지 않은 배치	그림 A.3: 올바른 배치

배치 하나를 받아 그것이 나이트 아홉 개 퍼즐의 올바른 해답인지 판정하라.

입력은 다섯 줄이고 각 줄은 다섯 글자다. 모든 글자는 나이트가 놓인 칸을 뜻하는 k 또는 빈 칸을 뜻하는 마침표 중 하나다.

주어진 판이 나이트 아홉 개 퍼즐의 올바른 해답이면 valid를 출력하고, 그렇지 않으면 invalid를 출력한다.