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.

Screen Shot 2022-11-01 at 12.03.36 PM.png

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
Sign in to continue