개선문 3

시간 제한: 1000 ms. 메모리 제한: 1024 MB.

코스타스 황제는 라이벌 맥스를 상대로 거둔 승리를 기념하기 위해 개선문을 세우려고 한다. 설계는 이미 끝났고, 이제 가능한 한 싸게 지어 줄 기술자를 찾고 있다.

개선문은 석재 블록으로 만든 좁은 구조물이다. 이 구조물은 2차원 단면으로 완전히 나타낼 수 있다. 예를 들어 로마에 있는 개선문 중 하나의 단면은 다음과 같다.

########
########
########
###..###
#.#..#.#
#.#..#.#

이 단면에서 #은 블록, .은 빈 공간을 뜻한다.

개선문이 서 있으려면 모든 블록이 안정 상태여야 한다. 블록은 다음 중 하나에 해당하면 안정 상태이다.

• 땅이나 다른 안정 상태 블록 위에 놓여 있다.
• 바깥쪽 블록이 안정 상태인 수평 블록 구간에 속한다.

예를 들어 다음 그림에서

########
########
##XAYZ##
###..###
B.#..#.#
C.#..#.#

블록 B는 안정 상태인 블록 C 위에 놓여 있으므로 안정하다(C는 땅 위에 있어 안정하다). 블록 A는 구간 XAYZ에 속하고, 이 구간의 바깥쪽 블록 X와 Z가 안정하므로 안정하다.

개선문은 블록을 하나씩 놓아서 지어진다. 공사 중 어느 순간에도 모든 블록은 안정 상태여야 한다. 따라서 임시 구조물 없이는 지을 수 없는 개선문이 있다. 위에 그린 개선문도 블록 A를 안정하게 놓을 방법이 없어서 임시 구조물 없이는 지을 수 없다.

그래서 기술자는 나무 블록으로 만든 임시 목재 구조물을 쓴다. 공사 중에도 같은 안정 조건이 적용된다. 블록은 하나씩 놓이며, 어느 순간에도 놓인 모든 블록은 안정 상태여야 한다. 안정성을 판단할 때 나무 블록과 석재 블록은 똑같이 취급한다.

따라서 위의 개선문은 나무 블록 3개로 지을 수 있다. 핵심 단계는 다음과 같다.

..####..
###^.###
#.#^.#.#
#.#^.#.#

(^은 나무 블록을 뜻한다.)

공사는 빈 칸에서 시작하여 다음 단계를 차례로 수행한다. 가능한 단계는 다음 세 가지이다.

• 선택한 칸에 석재 블록을 놓는다.
• 선택한 칸에 나무 블록을 놓는다.
• 선택한 칸에서 나무 블록을 치운다.

각 시점에 세워져 있는 블록은 모두 안정 상태여야 한다. 나무 블록은 비싸므로 코스타스는 가능한 한 적게 사려고 한다. 치운 나무 블록은 다시 쓸 수 있다.

나무 블록을 가장 적게 쓰면서 개선문을 지어라. 공사가 끝났을 때 석재 블록은 계획에 적힌 위치에 정확히 있어야 한다. 나무 블록은 남아 있어도 된다.

첫 줄에 공백으로 구분된 네 개의 수가 주어진다. 개선문의 너비 $M$, 높이 $N$, 그리고 점수 함수를 정하는 매개변수 $A$와 $B$이다.

이어지는 $N$개의 줄에 개선문이 위에서 아래로 차례로 적혀 있다. 각 줄에는 $M$개의 문자가 있으며, #은 블록, .은 빈 공간을 뜻한다.

공사 과정 전체를 출력하라. 각 단계마다 블록을 추가하거나 제거할 칸의 좌표를 공백으로 구분된 두 수로 한 줄에 출력한다. 그 칸에 아직 블록이 없었다면 블록이 놓인다.

• 계획에서 그 칸이 석재 블록이면 석재 블록이 놓인다.
• 계획에서 그 칸이 빈 공간이면 나무 블록이 놓인다.

그 칸에 이미 나무 블록이 있었다면 그 블록을 치운다.

$1 \le M, N \le 100$