403389: GYM101149 D Behind the Wall

Space marine officer Sarah and her small squad appeared to be on a hostile planet full of species of zorcs, an alien race known for their radical extremist views to other species. Fighting against zorcs would be a great disrespect to their rich culture so she wants to cover her base with a wall as soon as possible and then safely wait for the reinforcements promised by the command center.

The map of the temporarily safe area is a cell field of n rows, each consisting of m cells. The base is located in the c-th cell of the r-th row. Sarah has estimated that building a wall in the j-th cell of the i-th row takes a_i, j units of time. She thinks that zorcs cannot pass through the cell where a wall is built. It's required to build walls in such a way that zorcs can't reach the base from outside the cell field, moving only through cells that have a common side and that doesn't have a wall built on them. The walls must be built in a minimal possible time, taking into account that they are build consequently one after another, and no time passes between building walls in different cells. Of course, it's prohibited to build a wall in a cell with the base.

Sarah is wondering in which cells walls must be built. Luckily, she has a programmer in her squad who started to solve this task.

The first line contains four space-separated integers: n, m, r and c (3 ≤ n, m ≤ 50, 2 ≤ r ≤ n - 1, 2 ≤ c ≤ m - 1) — the height and width of the field, and the numbers of row and column where the base is located. Each of the next n lines contains m integers: a_i, j (0 ≤ a_i, j ≤ 500) — the number of time units needed to build a wall in the cell in the i-th row and the j-th column. It's guaranteed that a_r, c = 0.

In the first line output a single integer — the minimal number of time units required to build the walls.

Then output n lines of m characters each. In the i-th line, on the j-th position output «.», if the wall must not be built in this cell, or «X», if the wall must be built in this cell. If there are several correct building plans, output any of them.

3 4 2 2
9 1 1 9
1 0 9 1
9 1 1 9

6
.XX.
X..X
.XX.

3 3 2 2
1 0 1
9 0 6
1 8 1

23
.X.
X.X
.X.