Karla's Route

A map of an area is represented by a rectangular grid with M rows and N columns.

....vvvvv#..........
....vvvvv#....####..
...vvvvv#........#..
...vvvv#.........#..
...vvvv#...##sss.#..
...vvvvvvvv.#ssss#..
...vvvvvvvv###ss#...
...vvvvvvvv..#ss#sss
....vvvvvvv#.#..#sss
########...#.#ss#sss
...........#.#sss#ss
...........#.#...#ss
..##########.#...#ss
..#........#.#...#ss
....#......#.#......
....#........#......

The characters have the following meanings:

• .: empty square
• #: rock
• v: water
• s: forest

Karla starts in the upper-left square and must reach the lower-right square. In one move she may step to one of the four neighboring squares. She cannot cross rocks, and she does not want to swim through water or walk through forest.

To help her, you may build at most K bridges and burn at most L forest areas.

Each bridge is built only over water, must be horizontal or vertical, and may have any positive length. If two bridges intersect, they are stacked at the intersection, so Karla cannot transfer from one bridge to the other there.

Burning one forest area removes exactly one connected forest component. A forest area is a maximal set of forest squares where every two squares are connected by a path using only horizontal and vertical moves through forest squares.

Find bridges to build and forest areas to burn so that Karla can travel from the start to the destination.

The first line contains two integers M and N (1 <= M, N <= 50).

The second line contains two integers K and L (1 <= K, L <= 10).

Each of the next M lines contains N characters describing the map. The upper-left and lower-right squares are always empty.

Print the final map after building bridges and burning forest areas.

Use - for each square of a horizontal bridge, | for each square of a vertical bridge, and + for a square where two bridges intersect. A burned forest square must be printed as ., the same as an empty square. Every printed bridge must be built completely, and every printed burned forest area must be removed completely.

The input data guarantees that at least one valid final map exists, but it may not be unique.