040. Valid Sudoku
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sudoku is a popular number puzzle involving placing digits (1-9) in a 9 by 9 grid. A sudoku is considered valid if all of the following are true:

-All digits are integers from 1 to 9

-No number occurs in the same row twice

-No number occurs in the same column twice

-No number occurs in the same 3 by 3 box twice.

Given a sudoku board, print whether or not it is valid.

Input

The input consists of nine lines, each containing nine space-separated integers ranging from 1 to 9.

Output

If the sudoku is valid, output VALID, otherwise output INVALID.

Examples
Input
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
Output
VALID
Input
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9
Output
INVALID