포스텍에는 매일 학교 사람들의 건강을 책임져주는 포스텍 도수체조가 있다. 도수체조에는 총 $10^6$가지의 동작이 있다.

매일 아침마다 학생들은 운동장에 모여 $N$행 $M$열의 대열로 서서 도수체조를 진행한다. 그러나 체조의 동작이 너무 많아 학생들 중 그 누구도 순서를 외우지 못했다! 따라서 학생들은 첫 번째 순서에는 그냥 아무 동작이나 하고, 그 다음 $t \ge 2$번째 순서부터는, 모든 학생이 동시에 자신과 상하좌우로 인접한 학생 중 한 명을 고르고, 그 학생이 $t-1$번째 순서에 했던 동작을 따라 한다.

맨 앞에서 체조 구령을 부르던 포닉스는 학생들의 도수체조가 너무 무질서하다고 생각했지만, 정작 본인도 정확한 순서를 몰라 마땅히 통제를 할 수가 없었다. 그래서 포닉스는 모든 학생들의 동작이 통일될때까지 무한정 체조 구령을 부르기로 했다.

맨 앞줄에서 포닉스의 따가운 눈초리를 받으며 체조를 하던 찬우는 과연 이 포스텍 도수체조가 언젠가는 끝날 수 있을지 궁금해졌다. 찬우를 대신해 각 학생들의 첫 번째 동작을 보고, 언젠가 동작 통일이 되어 집에 가는게 가능한지 판단해주자.

입력 형식

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. 이는 학생들의 대열이 $N$행 $M$열임을 의미한다. ($ 1 \le N,M \le 1000$)

둘째 줄부터 $N$개의 줄에 걸쳐, $i+1$번째 줄에 $M$개의 정수 $A_{i,1}, A_{i,2}, \cdots, A_{i,M}$이 주어진다. $A_{i,j}$는 $i$행 $j$열에 있는 학생의 첫 번째 체조 동작을 의미한다. ($1 \le i \le N; 1 \le j \le M; 1 \le A_{i,j} \le 10^6 $)

출력 형식

각 순서마다 학생들이 인접한 학생을 적절히 선택하여, 어떤 시점에 모든 학생의 동작을 같게 만들 수 있다면 $\texttt{YES}$를, 그렇지 않다면 $\texttt{NO}$를 출력한다.

예제

예제 1

입력

2 2
1 5
5 7

출력

NO

예제 2

입력

3 4
1 2 3 4
5 3 2 1
3 2 4 5

출력

YES

예제 3

입력

1 1
1

출력

YES