M. Group Effect
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are playing a tower defense game where you can build two types of defensive towers in an $$$n \times m$$$ grid.

Each tower type has a base DPS (Damage Per Second): Tower A has a base DPS of $$$d_A$$$, and Tower B has a base DPS of $$$d_B$$$. As monsters will increase in later stages, you want to maximize the total DPS of all towers.

Additionally, each tower type has unique characteristics:

  • Group Effect (Tower A): For each Tower A, its DPS increases by $$$1$$$ for every adjacent Tower A (up, down, left, right). This effect stacks.
  • Isolation Effect (Tower B): For each Tower B, its DPS decreases by $$$1$$$ for every adjacent Tower B (up, down, left, right). This effect stacks, but the DPS will not drop below $$$0$$$.

Some grid cells are obstacles (marked as #) and cannot be used for building towers. The remaining cells are empty (marked as .), where you can build at most one tower per cell or leave them empty. How should you arrange the towers to maximize the total DPS?

Input

The first line contains four integers: $$$n$$$, $$$m$$$, $$$d_A$$$, $$$d_B$$$ ($$$1 \leq n,m \leq 2000$$$, $$$1 \leq d_A,d_B \leq 10^9$$$).

The next $$$n$$$ lines each contains $$$m$$$ characters(. or #), where . denotes an empty cell and # denotes an obstacle.

Output

The first line should output the maximum total DPS.

The next $$$n$$$ lines, each containing $$$m$$$ characters, should show the grid after tower placement, where A represents Tower A, B represents Tower B, and other symbols match the input.

Example
Input
3 3 2 8
...
#..
...
Output
46
BBB
#AA
BBB
Note

The DPS for each tower is shown as follows:

767
#33
767