Robotic Invasion

Time limit1sMemory limit128 MB

Summary

Edit as few commands as possible in a movement string so the robot reaches a trap, breaking ties by earliest capture and then lexicographic order.

Level: Hard8 of 10
Topics: BFS, Dynamic programming, Graph, Implementation
Solved: No attempts yet

Problem

The pacifist people of planet Pax are at war with the aggressors from planet Googol. Although they are strictly pacifist, they have means of defense: their cryptographers routinely decrypt the commands sent to Googol's robots and, at the cost of huge amounts of energy, can forge bogus commands. The Tactical Unit Defense (TUD) must find the best way to interfere with Googol's command transmissions.

You are given a map that contains a single invading robot and, possibly, several obstacles and traps, together with the string of movement commands originally sent to the robot. Each command is a step to the north, east, south, or west.

Your task is to overcome the threat by editing as few commands as possible so that the robot is guided into a trap. A single edit replaces one command with a different direction, or with no movement at all.

Movement rule. For a given command, the robot moves one cell in that direction only if the target cell lies inside the map and is not blocked; otherwise the robot stays where it is.

The robot is caught the moment it steps onto a trap.

Input

The first line contains the number of scenarios. Each scenario is given as follows:

A line with two integers $w$ and $h$ ( $1 \le w, h \le 100$ ), separated by a single space: the width and height of the map.
$h$ lines, each with $w$ characters, describing the map. Exactly one cell is R, the robot's starting cell. The other cells are . for a free cell, X for a blocked cell, and + for a trap.
A line with one integer $c$ ( $0 \le c \le 100$ ): the number of commands.
A line with $c$ characters, the original commands. Each character is N, E, S, or W, meaning move one cell up, right, down, or left, respectively.

Output

For each scenario, first print a line Scenario #i:, where i is the scenario number starting at 1.

Then, on the next line, print the edited command string that guides the robot into a trap. This string must have exactly $c$ characters, each being N, E, S, W, or X (where X means no movement). Among all strings that lead the robot into a trap, output:

one that edits as few of the original commands as possible; then
among those, one that makes the robot reach a trap as early as possible; then
among those, the lexicographically smallest string.

If no such string exists, print impossible instead.

Separate consecutive scenarios with a single blank line.

Examples3

Example 1

Input

3
3 2
R+.
...
3
EEE
3 3
R..
.X+
...
3
SSE
3 3
R..
..+
...
3
SSE

Expected output

Scenario #1:
EEE

Scenario #2:
EES

Scenario #3:
ESE

Example 2
Input
```
1
5 1
R...+
4
EEEE
```
Expected output
```
Scenario #1:
EEEE
```

Example 3

Input

1
3 3
R..
...
..+
4
NNNN

Expected output

Scenario #1:
EESS