Sudoku
Data una griglia di sudoku, devi verificare se sia valida.
Una griglia sudoku valida deve avere:
- Tutti i numeri da 1 a 9 in ciascuna riga.
- Tutti i numeri da 1 a 9 in ciascuna colonna.
- Tutti i numeri da 1 a 9 all’interno delle celle .
Di conseguenza, una griglia sudoku non valida potrebbe presentare:
- Numeri ripetuti in alcune righe.
- Numeri ripetuti in alcune colonne.
- Numeri ripetuti all’interno di alcune celle .

Input
L’input contiene una griglia di numeri. Tutti i numeri inseriti sono interi compresi tra 0 e 9. Le celle vuote sono rappresentate come 0.
Output
Il programma deve stampare
Valid
se la griglia è valida, altrimenti Not valid
. Esempi
Ingresso | Uscita |
0 0 0 0 0 8 0 0 2
0 7 0 0 0 0 0 1 0
0 2 0 7 0 0 9 0 0
0 0 0 0 0 0 7 0 1
0 0 0 9 0 2 6 0 0
3 0 5 8 0 0 0 4 0
9 0 0 6 0 0 4 0 0
0 0 0 2 0 7 0 6 0
0 0 1 0 0 4 0 0 0 | Valid |
0 0 0 0 0 8 0 0 2
0 7 0 0 0 0 0 1 0
0 2 0 7 0 0 9 0 0
0 0 0 0 0 0 7 0 1
0 6 0 9 0 2 6 0 0
3 0 5 8 0 0 0 4 0
9 0 0 6 0 0 4 0 0
0 0 0 2 0 7 0 6 0
0 0 1 0 0 4 0 0 0 | Not valid |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB