题目描述

1s，512M，water.in，water.out。

给定一个 $N\times M$ 的矩阵，你需要花费最少桶水使得整个矩阵被填满水。

根据 $\texttt{Minecraft}$ 的世界规则，如果当前格子为空，但与之相邻的格子中有至少 $2$ 个格子有水，则当前格子自动填充一格水。

一直填充下去直到不存在一个空格子有至少 $2$ 个相邻的格子有水。

形式化题意：给定一个 $N\times M$ 的矩阵，初始每个格子都是 $0$，你需要将一些格子变成 $1$。之后每一秒，如果存在一个为 $0$ 的格子，与它相邻的最多 $4$ 个格子中，有大于等于两个格子为 $1$，则该格子也会变成 $1$。问初始时至少需要将多少个格子变为 $1$，才能使得整个矩阵最后全部为 $1$。

注意：不需要使时间最短，如果有多个方案，则输出任意一个。

输入格式

一行两个数表示 $N,M$ 。

输出格式

第一行输出一个数表示填充的 $1$ 的数量。

接下来 $N$ 行输出一个 $N\times M$ 的 $0/1$ 矩阵，为 $1$ 表示这个位置填充了一格水，为 $0$ 表示留空。

如果有多个方案，任意输出一个即可。

样例 #1

样例输入 #1

1 2

样例输出 #1

2
1 1

样例 #2

样例输入 #2

1 3

样例输出 #2

2
1 0 1

样例 #3

样例输入 #3

3 3

样例输出 #3

3
1 0 1
0 0 0
0 1 0

提示

对于 $100\%$ 的数据，保证 $N\times M\le 10^6$。

• 子任务 1（10 分），$N,M\le 4$。
• 子任务 2（20 分），$N\times M\le 1000$。
• 子任务 3（30 分），$N = M$。
• 子任务 4（40 分），无特殊限制。