榻榻米

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的格子。

我们想用 $1 \times 1$ 和 $1 \times 2$ 的瓷砖覆盖这个网格,要求瓷砖互不重叠,且每个格子都被覆盖。(瓷砖可以旋转。)

每个格子上写着 1、2 或 ?。格子 $(i,j)$ 上写的字符为 $c_{i,j}$。

写着 1 的格子必须被 $1 \times 1$ 的瓷砖覆盖,写着 2 的格子必须被 $1 \times 2$ 的瓷砖覆盖。写着 ? 的格子可以被任意一种瓷砖覆盖。

判断是否存在这样的瓷砖摆放方式。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$
$c_{1,1}c_{1,2}\ldots c_{1,W}$
$\vdots$
$c_{H,1}c_{H,2}\ldots c_{H,W}$

输出格式

如果存在满足题目条件的瓷砖摆放方式,输出 Yes;否则输出 No。

样例

3 4
2221
?1??
2?21

Yes

例如,下面的摆放方式满足条件。

3 4
2?21
??1?
2?21

No

不存在满足条件的摆放方式。

5 5
11111
11111
11211
11111
11111

No

数据范围

• $1 \le H,W \le 300$
• $H$、$W$ 是整数。
• $c_{i,j}$ 是 1、2、? 之一。