칼라의 길

어떤 지역의 지도는 M행 N열의 직사각형 격자로 표현된다.

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

각 문자의 의미는 다음과 같다.

• .: 빈 칸
• #: 바위
• v: 물
• s: 숲

칼라는 왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 가야 한다. 한 번 이동할 때는 상하좌우로 인접한 칸 하나로 이동할 수 있다. 바위는 지나갈 수 없고, 물을 헤엄치거나 숲을 걸어서 지나가고 싶지도 않다.

칼라를 돕기 위해 최대 K개의 다리를 놓거나 최대 L개의 숲 영역을 태울 수 있다.

다리는 물 위에만 놓을 수 있으며, 가로 또는 세로 방향의 직선이어야 하고 길이는 양수라면 얼마든지 가능하다. 두 다리가 교차하면 교차 지점에서는 한 다리가 다른 다리 위에 놓이므로, 그 지점에서 한 다리에서 다른 다리로 갈아탈 수 없다.

숲 영역 하나를 태운다는 것은 연결된 숲 성분 하나를 정확히 지우는 것이다. 숲 영역은 숲 칸들로 이루어진 최대 집합이며, 그 안의 임의의 두 칸 사이를 숲 칸만 지나 상하좌우 이동으로 오갈 수 있어야 한다.

칼라가 출발점에서 도착점까지 갈 수 있도록 놓아야 할 다리와 태워야 할 숲 영역을 찾아라.

첫째 줄에 두 정수 M과 N이 주어진다 (1 <= M, N <= 50).

둘째 줄에 두 정수 K와 L이 주어진다 (1 <= K, L <= 10).

다음 M개의 줄에는 지도를 나타내는 길이 N의 문자열이 주어진다. 왼쪽 위 칸과 오른쪽 아래 칸은 항상 빈 칸이다.

다리를 놓고 숲 영역을 태운 뒤의 최종 지도를 출력한다.

가로 다리의 각 칸은 -, 세로 다리의 각 칸은 |, 두 다리가 교차하는 칸은 +로 표시한다. 태운 숲 칸은 빈 칸과 같이 .로 표시한다. 출력한 모든 다리는 완전히 놓여 있어야 하며, 태운 숲 영역도 전체가 완전히 지워져 있어야 한다.

입력 데이터는 유효한 최종 지도가 적어도 하나 존재하도록 주어진다. 단, 답이 유일할 필요는 없다.