Most console role-playing games, such as the famous Final Fantasy and Dragon Quest games, have towns filled with inconsequential characters that wander around aimlessly, waiting for the player to speak to them.
You've been tasked with the development of the town character (or NPC) movement handling for a new game.
Any given NPC has a movement script with a few simple commands:
|NORTH x||Move NORTH (up) x steps, one per turn|
|SOUTH x||Move south (down) x steps, one per turn|
|EAST x||Move east (right) x steps, one per turn|
|WEST x||Move west (left) x steps, one per turn|
|PAUSE x||Stay in the current location x turns|
...# .1.# ...#
if the NPC represented by the 1 hadEAST 5
as their next command, that would be converted on the fly toEAST 1
followed byPAUSE 4
. This processing must be done before determining whether a script iscyclic
A script is cyclic if, at the end of the script, the NPC back in their starting position. This sort of script is simply looped indefinitely. The other type of script is reversible; if, at the end of the script, the NPC is not back in their starting position, they then run a reversed copy of the script, with directions switched (WEST becomes EAST, EAST becomes WEST, NORTH becomes SOUTH, and SOUTH becomes NORTH) and PAUSEs intact. The end result is the character returning to their starting location.
|Original script segment||Reversed script segment|
| SOUTH 1
| WEST 1
For the sake of this problem, you can assume that no NPCs will ever attempt to occupy the same location on the map at the same time, although one may enter a location on the same turn as a different NPC leaves it, which is valid behavior.
The simulation starts at turn 0; your task is to show, given a map and set of NPCs with their scripts, what the simulation looks like after a large number of turns have passed.
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set consists of the following components:
For each data set in the output, output the heading "DATA SET #k" where k is 1 for the first data set, 2 for the second, and so on. the next H lines, output a representation of the town map, using the same symbols as the input format described above, with the NPCs in the correct locations after the given number of turns have passed.
1 2 5 5 ...#. .1.#. ...#. ...2. ..... 1 4 EAST 5 SOUTH 1 PAUSE 1 WEST 1 2 4 EAST 1 SOUTH 1 WEST 1 NORTH 1 22
DATA SET #1 ...#. ...#. ..1#. ..... ....2
|1000 MS||128 MB|