A. 访问级别

每个测试的时间限制：$2$ 秒
内存限制：$512$ 兆字节

BerSoft 是 Berland 最大的 IT 公司，Monocarp 是其安全部门的负责人。这一次，他面临着有史以来最困难的任务。

基本上，有 $n$ 个开发者在 BerSoft 工作，编号从 $1$ 到 $n$。内部网络上有 $m$ 份文档，编号从 $1$ 到 $m$。有一个访问需求表 $a$，其中 $a_{i,j}$（第 $i$ 行的第 $j$ 个元素）为 $1$ 表示第 $i$ 个开发者应该有权访问第 $j$ 份文档，为 $0$ 表示他们不应该有访问权限。

为了限制访问，Monocarp 将执行以下操作：

1. 选择访问组的数量 $k \ge 1$；
2. 为每份文档分配一个访问组（一个 $1$ 到 $k$ 的整数）和一个所需访问级别（一个 $1$ 到 $10^9$ 的整数）；
3. 为每个开发者分配 $k$ 个整数值（每个值在 $1$ 到 $10^9$ 之间）——他们在每个访问组中的访问级别。

如果开发者在文档所属的访问组中的访问级别 大于或等于 该文档的所需访问级别，则该开发者有权访问该文档。

Monocarp 最少可以选择多少个访问组，使得能够分配访问组和访问级别，从而满足访问需求表？

输入

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 500$）——开发者的数量和文档的数量。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串——访问需求表。第 $i$ 行的第 $j$ 个字符为 $1$ 表示第 $i$ 个开发者应该有权访问第 $j$ 份文档，为 $0$ 表示不应该有访问权限。

输出

第一行应包含一个整数 $k$ —— Monocarp 可以选择的最少访问组数量，使得能够分配访问组和访问级别来满足访问需求表。

第二行应包含 $m$ 个 $1$ 到 $k$ 的整数 —— 文档的访问组。

第三行应包含 $m$ 个 $1$ 到 $10^9$ 的整数 —— 文档的所需访问级别。

接下来的 $n$ 行，第 $i$ 行应包含 $k$ 个 $1$ 到 $10^9$ 的整数 —— 第 $i$ 个开发者在每个访问组上的访问级别。

如果存在多个解，输出任意一个即可。

样例

输入

3 2
01
11
10

输出

2
1 2
2 2
1 2
2 2
2 1

输入

2 3
101
100

输出

1
1 1 1
1 10 5
8
3

提示

在第一个样例中，我们将两份文档分配到不同的访问组。两个文档在其各自的访问组中的所需级别都是 $2$。这样，我们可以为需要访问的开发者分配级别 $2$，为不应有访问权限的开发者分配级别 $1$。

如果它们被分配到同一个访问组，那么将无法为开发者 $1$ 和 $3$ 分配访问级别。开发者 $1$ 在该组中应该比开发者 $3$ 有更低的级别，以便无法访问文档 $1$。同时，开发者 $3$ 在该组中应该比开发者 $1$ 有更低的级别，以便无法访问文档 $2$。由于他们不可能同时比对方级别低，因此只有一个访问组是不可能的。

在第二个样例中，可以将所有文档分配到同一个访问组。