31791번 - 바이러스 공격

문제

무시무시한 테러 단체 '타도 유해조류 산지니'가 부산대학교에 바이러스를 살포하겠다고 예고했다. $N$행 $M$열의 격자로 이루어진 부산대학교 위에는 $B$개의 건물이 구역 안에 겹치지 않고 있으며, 부산대학교의 철통같은 보안 덕에 테러 단체가 건물에는 바이러스를 살포하지 못한다.

테러에 사용될 바이러스는 아래의 세 가지 특징이 있다.

1. 건물의 내부와 외부에 존재하는 모든 바이러스는 살포 시점으로부터 $T_{G}$시간 뒤 전파를 멈춰 바이러스가 더 이상 주변으로 퍼지지 않는다.
2. 바이러스로부터 안전하지 않은 구역과 상하좌우로 인접한 구역은 1ドル$시간 뒤 바이러스의 전파가 완료되며, 전파가 완료되기 전까지 인접한 구역은 전파되지 않은 구역으로 간주한다. 두 구역이 서로 변을 공유할 때 인접한다고 한다.
3. 건물에 바이러스가 전파된 시점으로부터 $T_{B}$시간 동안은 건물 내부에 바이러스가 퍼진다. 이 기간 동안 건물 내부는 바이러스가 전파되지 않은 층으로 대피할 수 있어 안전하다. 바이러스가 전파된 지 $T_{B}$시간이 지난 뒤 모든 층에 바이러스가 전파되어 건물이 더이상 안전하지 않게 되면 마찬가지로 상하좌우로 인접한 구역에 1ドル$시간 뒤 바이러스가 전파된다.

하나의 구역은 격자의 한 칸을 의미하며, 바이러스가 전파되지 않은 구역과 바이러스가 전파된 시점으로부터 $T_{B}$시간이 지나지 않은 건물을 안전한 구역, 그 외 모든 구역을 안전하지 않은 구역으로 분류한다.

산지니는 테러에 부산대학교 학우들이 휩쓸리지 않도록 안전한 곳으로 대피시키고 싶어 한다. 바이러스를 피해 대피할 수 있는 구역을 구해주자.

입력

첫 번째 줄에 격자의 크기를 나타내는 정수 $N,ドル $M$이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 1,000円)$

두 번째 줄에 바이러스가 전파되는 시간 $T_{G},ドル 건물에서 전파가 지연되는 시간 $T_{B},ドル 처음 바이러스가 살포된 지점의 개수 $X,ドル 건물의 개수 $B$가 공백으로 구분되어 주어진다. $(1 \leq T_{B} \leq T_{G} \leq 2,000円; 0 \leq X, B \leq N \times M; 0 \leq X + B \leq N \times M)$

세 번째 줄부터 $N+2$번째 줄까지 도시의 상태를 나타내는 길이 $M$의 문자열이 주어진다. $i+2$번째 줄의 $j$번째 문자는 $i$행 $j$열의 상태를 나타낸다. 만약 문자가 *라면 바이러스가 살포된 곳, #라면 건물이 있는 곳, .라면 빈 곳을 의미한다.

주어지는 모든 수는 정수이다.

출력

도시 내에 안전한 구역이 없다면 -1을 출력한다.

도시 내에 안전한 구역이 있다면 안전한 구역들의 좌표를 행 번호가 증가하는 순으로, 행 번호가 같다면 열 번호가 증가하는 순으로 한 줄에 하나씩 출력한다.

행의 번호는 1ドル$ 이상 $N$ 이하의 정수, 열의 번호는 1ドル$ 이상 $M$ 이하의 정수로 출력한다.

제한

노트