A ceramics workshop fires glazed tiles on a square kiln rack with n x n slots arranged in a grid. Every slot holds a shelf tagged with an integer firing-profile label between 1 and n. A firing cycle is considered uniform only when every row of the rack contains each profile label from 1 to n exactly once, and every column of the rack also contains each profile label from 1 to n exactly once. Given the label grid recorded for one firing cycle, determine whether that cycle was uniform.

Input format

• Line 1: a single integer n, the number of rows (and columns) in the grid.
• Each of the next n lines contains n space-separated integers, where the j-th integer on the i-th of these lines is grid[i][j], the profile label of the slot in row i, column j (rows and columns are simply listed top-to-bottom, left-to-right in the input).

Output format

Print a single line containing exactly true if every row and every column of the grid contains each integer from 1 to n exactly once, or false otherwise.

Constraints

• 1 <= n <= 100
• 1 <= grid[i][j] <= n for every slot in the grid

3
1 2 3
3 1 2
2 3 1

true

3
1 1 2
1 2 3
2 3 3

false