2010 ACM ICPC South Central USA Regional Programming Contest

## D - Hoverdia Eighteen

Hoverdia Eighteen is a number puzzle game similar to Sudoku, which gets its name from the restrictions placed on the puzzle in horizontal, vertical, and diagonal directions. The game is played on an eight-by-eight grid. The game has two rules:

1. Each row and column must contain the numbers one through eight, inclusive, with no duplicates.
2. Each of the four-by-four quarters of the puzzle must contain numbers such that the sum of any row, column, or diagonal is eighteen.

Write a program to determine the validity of a proposed solution to this game.

 8 7 2 1 5 3 6 4 3 2 7 6 4 8 1 5 1 4 5 8 2 6 3 7 6 5 4 3 7 1 8 2 7 8 1 2 3 4 5 6 4 1 8 5 6 7 2 3 5 6 3 4 1 2 7 8 2 3 6 7 8 5 4 1

### Input

Input will consist of a number of test cases, t, followed by a definition of each test case. Each test case consists of a line containing the puzzle name (up to 80 printable characters) and is followed by 8 lines, each containing 8 digits separated by space(s). The digits range from 1-8.

### Output

Output a line for each test case, containing the puzzle name followed by “: ” and the word “valid” or “invalid”. Output “valid” if the puzzle satisfies the rules of an Eighteen puzzle. Output “invalid” if the puzzle violates the Eighteen puzzle rules.

### Sample Input

```2
PUZZLE ONE
8 7 2 1 5 3 6 4
3 2 7 6 4 8 1 5
1 4 5 8 2 6 3 7
6 5 4 3 7 1 8 2
7 8 1 2 3 4 5 6
4 1 8 5 6 7 2 3
5 6 3 4 1 2 7 8
2 3 6 7 8 5 4 1
PUZZLE TWO
1 7 2 1 5 3 6 4
3 2 7 6 4 5 1 8
8 4 5 8 2 6 3 7
6 5 4 3 5 1 8 2
7 8 1 2 3 4 5 6
4 1 8 5 6 7 2 3
8 6 3 4 1 2 7 5
2 3 6 5 7 8 4 1```

### Sample Output

```PUZZLE ONE: valid
PUZZLE TWO: invalid```