F: 紙の折りたたみ / Folding Paper

問題文

高さ $H$ マス、幅 $W$ マスの格子状に区切られた長方形の紙がある。 $0$ から数えて上から $i$ 行目、左から $j$ 列目のマスには整数 $i \times W+j$ が書かれている。 $H=2, W=3$ の例を下の図に示す。

AOR イカちゃんは、この紙に対して次のような操作を順に行った。

1. $1$ マス分の面積になるまでマスの区切り線に沿って繰り返し折る。この時の折る線や山谷、順番などは任意である。紙を破らない任意の折り方ができる。
2. $4$ 辺を切り落として $H \times W$ 枚の紙に分割する。
3. 上から順にめくっていき、書かれていた整数を並べた数列 $S$ を作る。

例えば、下の図のように折った後切った場合、$S$ として $4, 3, 0, 5, 2, 1$ が得られる。このように、間に差し込むような折り方も可能である。

あなたは AOR イカちゃんから数列 $S$ を受け取った。 しかし、AOR イカちゃんのことを信用していないので、これが本物か確かめたい。 $S$ と一致するような紙の折り方が存在するなら "YES" を、しないなら "NO" を出力するプログラムを書け。

入力

$H \ W$
$S_0 \cdots S_{HW-1}$

入力の制約

$1 \le H, W \le 500$
$S$ は $0$ から $H \times W - 1$ までの整数を $1$ つずつ含む

出力

"YES" または "NO" を $1$ 行で出力せよ。

サンプル

サンプル入力1

1 4
0 1 2 3

サンプル出力1

YES

サンプル入力2

2 3
4 3 0 5 2 1

サンプル出力2

YES

問題文中の例である。

サンプル入力3

1 4
0 2 1 3

サンプル出力3

NO

サンプル入力4

2 2
0 1 3 2

サンプル出力4

YES

$2$ 回半分に折る。

Note

Commentary

 

---