Artificial Strife

Conway's Game of Life is a simulation on a square grid of cells. Each cell is either alive or dead. Each turn is computed from the previous one: a cell's state in turn $n+1$ depends on its own state in turn $n$ together with the states of the eight cells surrounding it. In the standard Game of Life, a live cell stays alive if it has two or three live neighbours, and a dead cell becomes alive if it has exactly three live neighbours; otherwise the cell dies or stays dead. The figure below shows several generations of a simple but surprisingly intricate structure called a glider:

   0       1       2       3       4
....... ....... ....... ....... .......
....... ...A... ..AA... ..AA... .AAA...
..AAA.. ..AA... ..A.A.. .AA.... .A.....
..A.... ..A.A.. ..A.... ...A... ..A....
...A... ....... ....... ....... .......
....... ....... ....... ....... .......

After four turns the whole structure has moved one cell up and one cell to the left. Many far more complex structures exist in the Game of Life; one can even build a (very, very slow) Turing machine on the grid, or simulate the Game of Life within itself.

The rule for the original Game of Life is written as 23/3: a cell stays alive in turn $n+1$ if it had two or three live neighbours in turn $n$, and a dead cell becomes alive if it had exactly three live neighbours. Many other "Conway-like" rules can be written in the same notation. A rule such as /234 (every live cell dies, but a dead cell with two, three, or four neighbours becomes alive) is perfectly valid and quite interesting; rules with no "birth" values are also valid, though unsurprisingly dull. Your task is to simulate several such rules at the same time on the same grid.

Because more than one rule runs on the same grid, some clarifications are needed:

• Each cell can be occupied by at most one cell of one species (a species is a rule identified by a particular letter).
• Only cells of the same species count toward the next state of that species.
• When two or more species would place a live cell in the same location, the conflict is resolved as follows:
  1. If exactly one species would place a live cell there and all others leave it dead, that species' live cell is placed.
  2. If more than one species would place a live cell there, the species whose letter comes first in alphabetical order wins. (For example, if species B and species D would both place a live cell, the cell becomes species B.)
• Assume the board is surrounded by an infinite field of dead cells that can never become alive.

After running a simulation for a given number of turns, report the maximum and minimum population of each species.

The input begins with a line containing a single integer $n$, the number of simulations. Each simulation begins with a line containing three integers $X$ $Y$ $S$ ($1 \le X, Y \le 50$; $1 \le S \le 26$), where $X$ and $Y$ are the width and height of the board and $S$ is the number of species on the board. The next $Y$ lines give the board at turn 0 (a '.' is a dead cell and each uppercase letter is a live cell of the corresponding species). The following $S$ lines give the rule for each species (the first line is species A, the second is species B, and so on), each in the notation described above. The last line of the simulation is an integer $T$, the number of turns to simulate.

For each simulation, first print "Simulation #N", where N is the simulation number starting at 1. Then print $S$ lines, one per species, in the format "Species C: At most M live, at least L live.", where C is the species letter (starting at A), M is the largest number of that species alive in any turn (including turn 0), and L is the smallest number of that species alive in any turn (including turn 0).

The diagram below shows the initial state and the four following states of the second example simulation:

  0     1     2     3     4
..A.. ..... ..A.. ..... ..A..
..A.. .AAA. ..A.. .AAA. ..A..
..A.. ..... ..A.. ..B.. ..A..
..... ..B.. .BBB. .B.B. .B.B.
.BBB. .BBB. .BBB. .B.B. .B.B.

Notice that in turn 4 species A takes over a cell that would otherwise have remained species B.