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.`

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 |

Β