Oily Currents

One major problem with something like an oil spill is that the oil does not simply stay where it comes from. If we only had a big cloud of oil forming right above the ruptured oil well itself, that would still be a big problem, but it would be much easier to clean up. Instead, the oil spreads both under the water and on top of it, driven by wind, waves, and currents. Once it covers hundreds of square miles, it becomes much harder to clean. Here we use a simple model to compute the area that ends up covered by oil because of currents. For simplicity we consider only two dimensions and a bounded region; any oil that leaves that region is assumed never to return to it.

The current information is given as follows. For a 2-dimensional grid, each cell tells you the strength (from $0$ to $4$) and the direction (N, S, E, or W) of the current. For instance, 2N means that once this cell becomes contaminated with oil, within one time step the two cells immediately to the north of it also become contaminated. In general, a contaminated cell with strength $s$ and direction $d$ contaminates, in the next time step, every cell from $1$ up to $s$ cells away in direction $d$. Given the coordinates of the cell where the spill starts and the duration $t$ to simulate, output the map of the oil spread after those $t$ steps.

Here N means north (the row number decreases), S means south (the row number increases), E means east (the column number increases), and W means west (the column number decreases). Oil that spreads out of the grid disappears and never returns.

The first line contains the number $K$ of data sets. This is followed by $K$ data sets, each of the following form.

The first line of a data set contains five integers $x, y, x_0, y_0, t$. Here $1 \le x, y \le 100$ are the width and height of the map, $1 \le x_0 \le x$ and $1 \le y_0 \le y$ are the coordinates of the cell where the oil spill starts, and $0 \le t \le 100$ is the duration to simulate.

This is followed by $y$ lines, each consisting of $2x$ characters. The characters in columns $2j-1$ and $2j$ of line $i$ describe the current at position $(j, i)$. The first one (a digit between $0$ and $4$) is the strength, and the second one (N, S, E, or W) is the direction of the current.

For each data set, output Data Set x: on a line by itself, where $x$ is its number (starting from $1$). Then output the map after $t$ steps of the oil spill. The map consists of $y$ lines of $x$ characters each. The $j$-th character of line $i$ is a dot (.) if that cell was not reached by the oil, and X if it was reached. Output a blank line between consecutive data sets.