知名视频博主 Pasha 决定制作一个恶搞视频以增加他的订阅量。他选择了一家著名的家具店 IKEA 作为拍摄地点。

商店的一个大厅可以表示为一个 $n \times m$ 的网格。一些网格单元被沙发占据。目前所有的沙发都是折叠状态，因此每个沙发恰好占据两个相邻的单元格。没有两个沙发重叠，所以每个单元格最多被一个沙发占据。未被占据的单元格为空。

Pasha 决定尽可能多地展开沙发，以增加在大厅中行走的难度，并捕捉顾客的反应。当一个沙发被展开时，它会占据一个 $2 \times 2$ 的正方形区域，该区域包含最初被该沙发占据的两个单元格，以及另外两个由沙发展开方向唯一确定的单元格。

请帮助 Pasha 确定可以展开的沙发的最大数量，并输出应该展开哪些沙发的指令。

输入格式

第一行包含两个整数 $n$ 和 $m$ — 网格的大小 ($1 \le n, m \le 1000$)。

接下来的 $n$ 行描述了大厅。每行包含 $m$ 个字符。字符 “.” 表示空单元格。被沙发占据的单元格用小写或大写英文字母表示。同一个沙发占据的两个单元格用相同的字符表示。两个相邻沙发的单元格用不同的字符表示。如果沙发用小写字母表示，它会向上或向左展开。如果沙发用大写字母表示，它会向下或向右展开。

输出格式

第一行应包含一个整数 — 可以展开的沙发的最大数量。

接下来的 $n$ 行应包含 $m$ 个字符 — 展开沙发后的大厅描述。字符 “.” 表示空单元格。被沙发占据的单元格应由数字表示。同一个沙发占据的单元格应由相同的数字表示。两个相邻的沙发应由不同的数字表示。

样例

样例输入 1

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

样例输出 1

2
.11.
0022
0022
.11.

样例输入 2

3 4
.XX.
....
YYZZ

样例输出 2

1
.00.
.00.
1122

样例输入 3

3 4
.XX.
....
yyzz

样例输出 3

2
.00.
1122
1122