Problem I
Sudoku Verify

Photo by Colin M.L. Burnett. Retrieved from the Sudoku Wikipedia Page.

A Sudoku puzzle is a number puzzle that is played on a $9 \times 9$ grid of cells. These cells are grouped into nine ($9$) non-overlapping $3 \times 3$ regions, for a total of nine ($9$) cells per region. The regions are shown outlined in bold on the figure on the right.

The initial state of the grid has some of the cells filled in (black in the figure on the right). The objective is to use logical inferences to fill in the rest of the board. But there are rules for how to fill out the remainder of the board. The rules are as follows:

• Along every column, every number between $1$ and $9$ (inclusive) must appear exactly once.

• Along every row, every number between $1$ and $9$ (inclusive) must appear exactly once.

• In each $3 \times 3$ region, every number between $1$ and $9$ (inclusive) must appear exactly once.

You are given a completed Sudoku puzzle. Determine whether it is valid.

Input

Each row of the filled out Sudoku puzzle corresponds to one line of input. The numbers of each row are separated by a single space. This encoding leads to an input with exactly nine ($9$) lines each of which contains exactly nine ($9$) numbers between $1$ and $9$ inclusive.

Output

If the Sudoku board is valid, output the text “VALID” (without the quotes).

If the Sudoku board is not valid, output the text “INVALID!” (without the quotes).

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

VALID

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

INVALID!