問題 I 山

問題文

L 氏はある都市の市長である．L 氏の市長としての手腕はすさまじく時を止め一瞬にして都市中に鉄道網を引いたり，財政の赤字を一夜にして莫大な黒字にしたり，はては巨大な怪獣をどこからともなく呼んでパフォーマンスに使うこともした．

そんな L 氏は土地の隣り合った行または列同士を何度も入れ替えることででこぼこな土地を山形にするという遊びを最近発明した．土地は H×W 個のブロックに区切られており，ブロック (y,x) では海面からの高さが h_y,x であると測定されている．入れ替え後のブロック (y,x) の高さを h'_y,x と書くことにする．この土地が山形であるとは，以下の図のように，あるブロック (y^*,x^*) があって，そこを山頂として山頂から離れるに従って高さが単調減少しているものをいう．

h'y^*-1, x^*-2	<	h'y^*-1, x^*-1	<	h'y^*-1, x^*	>	h'y^*-1, x^*+1	>	h'y^*-1, x^*+2
∧		∧		∧		∧		∧
h'y^*, x^*-2	<	h'y^*, x^*-1	<	h'y^*, x^*	>	h'y^*, x^*+1	>	h'y^*, x^*+2
∨		∨		∨		∨		∨
h'y^*+1, x^*-2	<	h'y^*+1, x^*-1	<	h'y^*+1, x^*	>	h'y^*+1, x^*+1	>	h'y^*+1, x^*+2

入力形式

最初の行に H と W がスペース区切りで与えられる．

次の H 行に土地の高さが与えられる． 各行は W 個の数値からなり，それぞれ対応する場所の高さを表す．

出力形式

土地を山形にできるなら "YES"，できないなら "NO" を出力せよ．

制約

• 1 ≤ H,W ≤ 1,000
• 0 ≤ h_y,x ≤ 10⁸
• 全ての h_y,x は相異なる．

入出力例

入力例 1

3 3
1 3 2
7 9 8
4 6 5

出力例 1

YES

入力例 2

以下の例では 2 番目の列と 3 番目の列を入れ替えることにより土地を山形にすることができる．

3 3
9 3 6
8 2 5
7 1 4

出力例 2

YES

入力例 3

1 1
100

出力例 3

YES

入力例 4

3 3
1 3 2
4 6 5
7 8 9

出力例 4

NO

謝辞