#212나이트 투어

나이트 투어는 체스판 위에서 나이트가 모든 칸을 정확히 한 번씩 방문하고, 마지막 칸에서 다시 출발점으로 돌아올 수 있는 경로를 말한다.

도윤이는 6×6 크기의 체스판에서 나이트 투어 경로를 찾아보려고 한다. 체스판의 각 칸은 다음과 같이 가로 방향으로 A부터 F까지, 세로 방향으로 1부터 6까지의 기호를 조합하여 나타낼 수 있다.

   A  B  C  D  E  F
1  .  .  .  .  .  .
2  .  .  .  .  .  .
3  .  .  .  .  .  .
4  .  .  .  .  .  .
5  .  .  .  .  .  .
6  .  .  .  .  .  .

예를 들어 'C4'는 가로 C, 세로 4에 해당하는 칸을 의미한다. 도윤이의 나이트 투어 경로가 주어졌을 때, 이 경로가 올바른 나이트 투어이면 Valid를, 그렇지 않으면 Invalid를 출력하는 프로그램을 작성하시오.

36개의 줄에 걸쳐 나이트가 방문한 순서대로 칸의 좌표가 주어진다. 입력으로는 체스판에 실제로 존재하는 칸만 주어진다.

첫째 줄에 경로가 올바른 나이트 투어인지 여부를 Valid 또는 Invalid로 출력한다.