An n-by-n Latin square is a grid filled with the integers 1..n such that each row and each column contains every value exactly once.
You are given a partially filled n-by-n grid: each cell holds either 0 (meaning empty) or a fixed value from 1 to n. It is guaranteed that the given fixed values contain no repeat within any single row and no repeat within any single column. Determine whether the empty cells can be filled in (each with a value from 1 to n) so that the completed grid is a valid Latin square.
Input format
Line 1: an integer n.
Next n lines: n space-separated integers each (0 for empty, otherwise 1..n) — the rows of the grid, top to bottom.
Output format
Print 1 if the grid can be completed to a full Latin square, otherwise print 0.
Constraints
- 2 ≤ n ≤ 4
- No non-zero value repeats within any row or within any column of the given grid.