Algorithms and Data Structures

Sudoku

Given a sudoku grid, you are asked if it’s a valid one.
A valid sudoku grid should have:
  • All the numbers from 1 to 9 on each row.
  • All the numbers from 1 to 9 on each column.
  • All the numbers from 1 to 9 inside the cells.
So, the invalid sudoku grid might have:
  • Some repeating numbers on some rows
  • Some repeating numbers on some columns
  • Some repeating numbers inside the cells.
notion image

Input

The input contains a grid of numbers. All the filled numbers are integers from 0 to 9. The empty cells are represented as 0s.

Output

The program should print Valid in case the grid is valid and Not valid otherwise.

Examples

Input
Output
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

To check your solution you need to sign in