Cossack Vus and Friend at CP Olympiad

Once Cossack Vus had to monitor his friend's participation in a competitive programming olympiad.

There are $m$ problems at the olympiad, each of which is scored as an integer from $0$ to $100$. If a participant solves a problem and receives $x$ points at time $t_0$, then at any time $t\ge t_0$, the number of points for that problem will not be less than $x$.

Cossack Vus was busy that day, so he couldn't keep track of his friend's results. Therefore, he decided to take screenshots of the screen every $10$ minutes of the olympiad. In total, he took $n$ screenshots. Each screenshot shows the number of points his friend had at a certain time.

Unfortunately, all the screenshots got mixed up in Vus's gallery. Your task is to determine if the order of the screenshots in the gallery is possible.

Input

The first line contains two integers $n$, $m$ ($1\le n,m\le 3000$) — the number of screenshots and the number of problems, respectively.

Each of the next $n$ lines contains $m$ integers $a_{ij}$ ($0\le a_{i,j}\le 100$) — the number of points for problem $j$ on the $i$-th screenshot.

Output

Output «Yes» if the screenshots in the gallery are in the same order as the time they were taken, and «No» otherwise.

Examples

Note

In the first test, there were $5$ problems at the olympiad and it lasted for $60$ minutes. The answer is «Yes» because the events could have occurred in the following order:

• in the first $10$ minutes, Vus's friend solved the first problem and scored $15$ points;

• in the next $10$ minutes, he solved the second problem and scored $30$ points;

• then he tried to solve the second problem again and managed to score $70$ points;

• after that, he attempted the last problem and scored $100$ points;

• then he solved the third problem and scored $25$ points;

• in the last $10$ minutes, he couldn't solve anything.

One reason why the answer is «No» in the second test is that in the first $10$ minutes, he solved the first problem and scored $97$ points, but in the last $10$ minutes, he somehow had only $2$ points, which is not possible.

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that the evaluation is still in the testing phase.

1. ($50$ points): $n,m\le 100$;

2. ($50$ points): without additional constraints.