틱택토

틱택토는 두 사람이 번갈아 말을 놓는 게임이다. 게임판은 3×3 격자이며 처음에는 모든 칸이 비어 있다. 첫 번째 사람은 항상 X를, 두 번째 사람은 항상 O를 놓으며, 두 사람은 한 칸씩 번갈아 말을 놓는다.

어느 순간이든 한 사람의 말이 가로, 세로, 또는 대각선 방향으로 한 줄(3칸)을 모두 채우면 그 사람이 이기고 게임은 즉시 끝난다. 아무도 한 줄을 완성하지 못한 채 9칸이 모두 채워지면 비긴 상태로 게임이 끝난다.

게임판의 상태가 하나 주어질 때, 그 상태가 위 규칙을 따르는 실제 틱택토 게임이 끝났을 때 나올 수 있는 상태인지 판별하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 9개의 문자로 주어지며, 각 문자는 X, O, . 중 하나이다(.은 빈 칸을 뜻한다). 9개의 문자는 게임판의 맨 윗줄부터 아랫줄까지, 각 줄에서는 왼쪽에서 오른쪽 순서로 나열한 것이다. 입력의 마지막 줄에는 문자열 end가 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄씩 출력한다. 해당 상태가 실제 게임이 끝났을 때 나올 수 있는 상태이면 valid를, 그렇지 않으면 invalid를 출력한다.