Sort the Table

Interview

Time limit2sMemory limit512 MB

Summary

Given an N by M grid holding a permutation of 1 to N*M, decide whether swapping whole rows and whole columns can make the row-major reading order sorted ascending.

Level: Medium6 of 10
Topics: Sorting, Implementation, Matrix, Greedy
Solved: No attempts yet

Problem

Yeongseon has a table with $N$ rows and $M$ columns. The rows are numbered $0$ to $N-1$ from top to bottom, and the columns are numbered $0$ to $M-1$ from left to right.

Each cell holds one positive integer, and the numbers in the table form a permutation of $1$ to $N \times M$ . Every number appears exactly once.

Read the cells row by row starting from the first row, and inside a row from left to right. The sequence you get is called the value sequence.

Yeongseon can modify the table in two ways. She can swap the positions of any two rows, or swap the positions of any two columns. She can use each operation as many times as she wants, in any order.

Given the table, write a program that decides whether the value sequence can be made ascending.

Input

The first line contains $N$ and $M$ . ( $1 \le N, M \le 50$ )

Each of the next $N$ lines contains $M$ numbers, the contents of the table.

Output

Print $1$ if the value sequence can be made ascending, and $0$ otherwise.

Examples5

Example 1
Input
```
2 2
1 2
3 4
```
Expected output
```
1
```
Example 2
Input
```
2 2
3 4
1 2
```
Expected output
```
1
```
Example 3
Input
```
2 2
4 3
1 2
```
Expected output
```
0
```
Example 4
Input
```
1 10
4 5 1 2 9 8 3 10 7 6
```
Expected output
```
1
```

Example 5

Input

3 5
10 6 8 9 7
5 1 3 4 2
15 11 13 14 12

Expected output