← 返回题目列表

Codeforces · 1157/G

G. 行和列的逆

中文机器翻译题面 查看原题

给定一个二进制矩阵 $$$a$$$,大小为 $$$n \times m$$$。二元矩阵是每个元素为 $$$0$$$ 或 $$$1$$$ 的矩阵。

您可以对此矩阵执行一些(可能为零)运算。在每次操作期间,您可以反转该矩阵的行或该矩阵的列。形式上,反转行是将这一行中的所有值更改为相反的值($$$0$$$ 更改为 $$$1$$$、$$$1$$$ 更改为 $$$0$$$)。反转列就是将该列中的所有值更改为相反的值。

您的任务是通过此类操作的某些序列对初始矩阵进行排序。如果数组 $$$[a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, a_{n, m - 1}, a_{n, m}]$$$ 按非降序排序,则认为矩阵已排序。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 200$$$) — 矩阵中的行数和列数。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数。第 $$$i$$$ 行中的第 $$$j$$$ 元素是 $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 1$$$) — $$$a$$$ 在位置 $$$(i, j)$$$ 处的元素。

输出

如果无法获得排序矩阵,则在第一行打印“NO”。

否则在第一行打印“YES”。在第二行中打印长度为$$$n$$$的字符串$$$r$$$。如果矩阵的第 $$$i$$$ 行反转,则该字符串的第 $$$i$$$ 个字符 $$$r_i$$$ 应为“1”,否则应为“0”。在第三行中打印长度为$$$m$$$的字符串$$$c$$$。如果矩阵的第 $$$j$$$ 列反转,则该字符串的第 $$$j$$$ 个字符 $$$c_j$$$ 应为“1”,否则应为“0”。如果有多个答案,您可以打印任何一个。

示例

输入 #1

2 2
1 1
0 1

输出 #1

YES
00
10

输入 #2

3 4
0 0 0 1
0 0 0 0
1 1 1 1

输出 #2

YES
010
0000

输入 #3

3 3
0 0 0
1 0 1
1 1 0

输出 #3

NO