기름 해류

기름 유출 같은 사고의 큰 문제점 중 하나는, 기름이 유출된 자리에 가만히 머무르지 않는다는 것이다. 만약 파열된 유정 바로 위에 기름 구름이 뭉쳐 있기만 한다면, 그것만으로도 큰 문제이긴 하지만 훨씬 치우기 쉬울 것이다. 그러나 실제로는 바람과 파도, 해류 때문에 기름이 물속과 수면 위로 함께 퍼져 나간다. 기름이 수백 제곱마일을 덮게 되면 정화하기가 훨씬 어려워진다. 여기서는 간단한 모형을 사용해, 해류 때문에 기름으로 덮이게 되는 영역의 넓이를 계산한다. 문제를 단순화하기 위해 2차원 평면의 유한한 영역만 고려하며, 그 영역을 벗어난 기름은 다시 돌아오지 않는다고 가정한다.

해류 정보는 다음과 같은 형태로 주어진다. 2차원 격자의 각 칸에는 해류의 세기($0$부터 $4$까지)와 방향(N, S, E, W)이 적혀 있다. 예를 들어 어떤 칸이 2N이라면, 그 칸이 기름으로 오염된 뒤 한 시간 단계 안에 그 칸의 바로 북쪽 두 칸도 함께 오염된다는 뜻이다. 일반적으로, 세기가 $s$이고 방향이 $d$인 오염된 칸은 다음 시간 단계에 방향 $d$로 $1$칸부터 $s$칸까지의 모든 칸을 오염시킨다. 기름이 처음 유출되는 칸의 좌표와 시뮬레이션할 시간 $t$가 주어질 때, $t$번의 시간 단계가 지난 뒤 기름이 퍼진 지도를 출력하여라.

여기서 N은 북쪽(행 번호가 감소), S는 남쪽(행 번호가 증가), E는 동쪽(열 번호가 증가), W는 서쪽(열 번호가 감소)을 뜻한다. 격자 밖으로 퍼져 나간 기름은 사라지며 다시 돌아오지 않는다.

첫 번째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 각각 다음 형태로 주어진다.

각 데이터 집합의 첫 줄에는 다섯 정수 $x, y, x_0, y_0, t$가 주어진다. $1 \le x, y \le 100$은 지도의 너비와 높이이다. $1 \le x_0 \le x$, $1 \le y_0 \le y$는 기름 유출이 시작되는 칸의 좌표이다. $0 \le t \le 100$은 시뮬레이션할 시간이다.

그 다음 $y$개의 줄이 주어지며, 각 줄은 $2x$개의 문자로 이루어진다. $i$번째 줄의 $2j-1$번째와 $2j$번째 문자는 위치 $(j, i)$의 해류를 나타낸다. 앞 문자($0$부터 $4$까지의 숫자)는 해류의 세기이고, 뒤 문자(N, S, E, W 중 하나)는 해류의 방향이다.

각 데이터 집합에 대해, 먼저 그 번호 $x$(1부터 시작)를 사용하여 Data Set x:를 한 줄에 출력한다. 이어서 $t$번의 시간 단계가 지난 뒤의 기름 지도를 출력한다. 지도는 각 줄이 $x$개의 문자로 이루어진 $y$개의 줄이다. $i$번째 줄의 $j$번째 문자는, 해당 칸이 기름에 닿지 않았으면 마침표(.), 닿았으면 X이다. 연속한 두 데이터 집합 사이에는 빈 줄을 하나 출력한다.