你正在玩一款塔防游戏，可以在一个 $n \times m$ 的网格中建造两种防御塔。

每种防御塔都有一个基础 DPS（每秒伤害）：塔 A 的基础 DPS 为 $d_A$，塔 B 的基础 DPS 为 $d_B$。由于后续关卡中的怪物会变强，你希望最大化所有防御塔的总 DPS。

此外，每种防御塔都有其独特的属性：

• 群聚效应（塔 A）：对于每个塔 A，每有一个相邻的塔 A（上、下、左、右），其 DPS 就会增加 1。此效果可叠加。
• 孤立效应（塔 B）：对于每个塔 B，每有一个相邻的塔 B（上、下、左、右），其 DPS 就会减少 1。此效果可叠加，但 DPS 不会降至 0 以下。

某些网格单元格是障碍物（标记为 #），不能用于建造防御塔。其余单元格为空地（标记为 .），你可以在每个空地单元格中最多建造一座防御塔，也可以选择留空。你应该如何安排防御塔以最大化总 DPS？

输入格式

第一行包含四个整数：$n, m, d_A, d_B$（$1 \le n, m \le 2000, 1 \le d_A, d_B \le 10^9$）。

接下来的 $n$ 行，每行包含 $m$ 个字符（. 或 #），其中 . 表示空地，# 表示障碍物。

输出格式

第一行输出最大总 DPS。

接下来的 $n$ 行，每行包含 $m$ 个字符，表示放置防御塔后的网格，其中 A 代表塔 A，B 代表塔 B，其他符号与输入保持一致。

样例

输入样例 1

3 3 2 8
...
#..
...

输出样例 1

46
BBB
#AA
BBB

说明

每个防御塔的 DPS 如下所示：

7 6 7
# 3 3
7 6 7