题目描述

知名视频博主 Pasha 决定拍摄一个恶作剧视频来增加订阅数。他选择了一家著名家具商店 IKEA 作为拍摄地点。

商店中的一个大厅可以表示为一个 $n\times m$ 的网格。一些格子被沙发占据。

当前所有沙发都是折叠状态，因此每张沙发恰好占据两个相邻格子。任意两张沙发不相交，所以每个格子最多被一张沙发占据。没有被占据的格子为空。

Pasha 想展开尽可能多的沙发，使顾客在大厅中行走变得困难，然后拍下他们的反应。

当一张沙发展开时，它会占据一个 $2\times 2$ 的正方形。这个正方形包含该沙发原本占据的两个格子，以及由沙发展开方向唯一确定的另外两个格子。

请帮助 Pasha 计算最多可以展开多少张沙发，并输出应该如何展开。

输入格式

第一行输入两个整数 n 和 m，表示网格大小。

接下来 n 行描述大厅，每行包含 m 个字符。

• . 表示空格子；
• 小写或大写英文字母表示被沙发占据的格子。

同一张沙发原本占据的两个相邻格子用相同字符表示。

相邻的两张沙发使用不同字符表示。

如果一张沙发用小写字母表示，那么它会向上或向左展开；如果用大写字母表示，那么它会向下或向右展开。

具体地，展开方向由沙发当前占据的两个相邻格子的方向以及字母大小写唯一确定。

输出格式

第一行输出一个整数，表示最多能展开的沙发数量。

接下来输出 n 行，每行 m 个字符，表示沙发展开后的大厅。

• . 表示空格子；
• 被沙发占据的格子应使用数字表示；
• 同一张沙发占据的格子应使用相同数字；
• 相邻的两张沙发应使用不同数字。

样例

样例 1

样例输入：

4 4
.AA.
A..a
A..a
.aa.

样例输出：

2
.11.
0022
0022
.11.

样例 2

样例输入：

3 4
.XX.
....
YYZZ

样例输出：

1
.00.
.00.
1122

样例 3

样例输入：

3 4
.XX.
....
yyzz

样例输出：

2
.00.
1122
1122