#P18014. Cell Flip Game

Cell Flip Game

Cell Flip Game

给定一个 n×mn\times m 的二进制矩阵 AA。

一次操作可以选择一个格子 (i,j)(i,j),将该格子以及与它共边相邻的所有格子的值翻转,即将 00 变成 11,将 11 变成 00。等价地,翻转所有满足 ∣s−i∣+∣t−j∣≤1|s-i|+|t-j|\le1 且位于矩阵内的格子 (s,t)(s,t)。

请构造一组操作,使矩阵的所有元素都变成 00,或者判断无解。

输入格式

第一行两个整数 n,mn,m。接下来 nn 行,每行一个长度为 mm 的二进制字符串,表示矩阵的一行。

输出格式

若无解,输出一行 NO。

否则第一行输出 YES,接下来输出 nn 行,每行一个长度为 mm 的二进制字符串。字符 1 表示要对对应格子执行一次操作,0 表示不执行操作。所有操作共同作用后,原矩阵必须全为零。

若有多种方案,任意合法方案均可。YES 和 NO 不区分大小写。

数据范围

1≤n,m≤5001\le n,m\le500。

样例 1

输入

3 4
1000
0001
0100

输出

YES
0100
0110
1100