题目描述

Petya 最近买下了一块矩形土地，准备在上面建一座从上方看起来像字母 C 的房子。

土地被划分成一个 $N\times M$ 的方格，每个格子大小为 $1\times1$。一些格子里长有树，房屋不能占用这些格子。

房屋由三个矩形块组成，分别记为上部、中部和下部，并满足：

1. 三个矩形的面积都必须大于 $0$；
2. 上部与中部相接，中部与下部相接，三个矩形不能重叠；
3. 三个矩形左上角所在格子的列坐标相同，即三个矩形的左边界在同一条竖线上；
4. 中部矩形的宽度必须严格小于上部矩形和下部矩形的宽度；
5. 房屋只能建在没有树的格子上。

Petya 希望房屋的总面积尽可能大。

请你求出最大可能面积，并给出任意一种达到最大面积的建造方案。

输入格式

第一行包含两个整数 $N,M$：

$1\le N,M\le180$。

接下来 $N$ 行，每行包含 $M$ 个整数，每个整数为 0 或 1：

• 0 表示该格子为空；
• 1 表示该格子中有树。

输出格式

如果不存在合法方案，只输出一行：

-1

否则：

• 第一行输出房屋能够达到的最大总面积；
• 接下来输出 $N$ 行，每行 $M$ 个整数，表示建造方案。

输出网格中：

• 原来有树的格子仍输出 1；
• 被房屋占用的空格输出 8；
• 其余空格输出 0。

如果有多种最优方案，输出任意一种即可。

样例 1

样例输入

8 7
1 1 1 1 1 1 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 0 0 0 0 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

样例输出

19
1 1 1 1 1 1 1
1 1 8 8 8 8 1
1 1 8 8 8 8 1
1 1 8 8 8 0 1
1 1 8 8 8 8 1
1 1 8 8 8 8 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1

样例 2

样例输入

8 8
1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 1
1 1 1 1 0 0 0 1
1 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1
1 0 1 0 1 0 0 1
1 0 0 0 0 0 1 1
1 1 1 1 1 1 1 1

样例输出

12
1 1 1 1 1 1 1 1
1 0 0 0 0 1 0 1
1 1 1 1 0 0 0 1
1 0 0 8 8 8 8 1
1 1 0 8 8 8 8 1
1 0 1 8 1 0 0 1
1 0 0 8 8 8 1 1
1 1 1 1 1 1 1 1