← К соревнованиям

Sort Me Round

Пятнашки 2.0

Вам дана матрица размером n×mn \times m клеток, все элементы которой различны и являются наутральными числами от 11 до nmnm.

Вы можете взять любой квадрат размером 2×22 \times 2 клетки и "прокрутить" его направо. Например, из квадрата

Получится

Назовем отсортированным состоянием матрицы aa состояние, когда при любых ii и jj выполняются условия a[i][j]>a[i][j1]a[i][j] > a[i][j - 1], a[i][j]>a[i1][m]a[i][j] > a[i - 1][m].

Можно ли только с помощью вышеописанной операции, применённой сколько угодно раз, привести заданную матрицу в отсортированное состояние?

Входные данные

В первой строке записаны числа nn и mm (2n,m5002 \le n, m \le 500; nm1000n \cdot m \le 1000) - количество строк и столбцов в матрице.

В следующих nn строках записано по mm чисел - элементы матрицы.

Выходные данные

В единственной строке выведите YES, если матрицу можно привести в отсортированное состояние, и NO в противном случае.

Подзадачи

баллынеобх. подзадачиограничения
1

70

-

nm20n \cdot m \le 20

2

30

1

Нет доп. ограничений

STDINSTDOUT
3 3
1 3 6
2 8 5
4 7 9
YES