#P2304F. Project of pulling water

Project of pulling water

背景

众所周知,在 Minecraft\mathtt{Minecraft} 的游戏规则中,如果有一个格子内没有满格水,但是其相邻两个格子都有满格水,那么这个格子会被自动填入满格水。

一天,杰神 和 Ocean 在 Minecraft\mathtt{Minecraft} 中新建了一个世界,准备一起联机。但是不幸的是,出生点是一片偌大的沙漠!

所幸,两人在游戏开始前加了一个神奇的模组,他会在玩家出生时给玩家一些水桶。

显然,通过本题背景的第一句话,我们可以很轻松地构造出一个无限水源,但是杰神觉得有点太无聊了。

相反地,杰神 给 Ocean 划分了一片 n×mn \times m 的区域,并希望 Ocean 在不使用区域内的无限水的条件下,用尽可能少的水桶将这个区域填满满格水。

你能帮 Ocean 想出一个合适的方案么?

image

说明

更正式地说:

首先,给定一个大小为 n×mn \times m 的矩阵,矩阵内所有元素初始都为 00

接着,你需要选择尽可能少的格子,将格子内的值修改为 11

最后,系统会按照 "如果一个格子的值为 00,并且其相邻的 44 个格子中,至少有两个格子的值为 11,那么这个格子的值会被修改为 11" 的规则,执行操作,直到不能操作为止。

你需要满足最后整个矩阵都是 11

输出满足上述条件的一种修改方案,以修改后的矩阵形式输出,并给出修改的格子数量。

输入格式

输入只包含一行两个整数,依次为 n,mn,m,表示给定矩阵的大小。

输出格式

第一行输出一个整数,代表修改的格子数量。

接下来输出 nn 行,每行输出 mm 个整数,代表矩阵的信息。

样例

样例输入1

2 1

样例输出1

2
1
1

样例输入2

3 3

样例输出2

3
1 0 1
0 0 0
0 1 0

提示

1n×m1061 \leq n \times m \leq 10^6