PION Snake Game Simulation

The game is played on an n × m grid. Each cell is one of the following characters:

• . represents an empty cell,
• # represents a snake body segment,
• @ represents a snake head, and
• & represents food.

In the initial board, there is exactly one snake (which may have length 1 or more) and zero or more pieces of food. The snake is represented by a single @ for its head and one or more # for its body. For a snake of length at least 2, the head is adjacent (in one of the four cardinal directions) to its first body segment. The snake body is a continuous chain.

You will simulate the snake movement for T seconds according to the following rules:

1. At each second, the snake moves once according to a given command. The commands are given as a string of length T and each character is one of W (up), S (down), A (left) or D (right). The move vector is as follows:
   \(W = (-1, 0)\), \(S = (1, 0)\), \(A = (0, -1)\), \(D = (0, 1)\).
2. If the snake has length at least 2, its current movement direction is defined as the vector from its second segment to its head. If a command instructs the snake to move in the exact opposite direction of its current movement (i.e. a reversal), the snake immediately dies.
3. After a valid move command (i.e. not a reversal), let the new head position be computed by adding the move vector to the current head position. If this new position is outside the grid boundaries, the snake dies.
4. Otherwise, if the new cell contains food (denoted by &), the snake eats the food and its length increases by 1. In this case, the food cell becomes the new head and the previous head becomes a body segment. No tail removal occurs during a growth move.
5. If the new cell is empty (denoted by .), the snake moves forward: the new head is added at the front and the tail cell is removed. Note: during an empty move, if the new head position coincides with the cell that is about to be removed (i.e. the tail), it is not considered a collision.
6. If the new cell is already occupied by any part of the snake (body or head), a collision occurs and the snake dies.
7. When the snake dies (by any cause), every cell that was occupied by any part of the snake (head and body) instantly turns into food (i.e. become &), and no further moves are executed.

After executing all commands (or upon death), output the final grid configuration. In the final grid, the snake, if alive, is drawn with its head as @ and the rest of its body as #. Any food remains as &, and all other cells are ..

Note: All formulae must be written using LaTeX format. For example, an \(n \times m\) grid, and move vectors \(W=(-1,0)\), \(S=(1,0)\), \(A=(0,-1)\), \(D=(0,1)\).

inputFormat

The first line contains three integers n, m, and T \( (1 \leq n,m \leq 100, 1 \leq T \leq 1000)\), representing the number of rows, columns, and the number of seconds to simulate.

The following n lines each contain a string of length m representing the initial grid configuration.

The last line contains a string of length T consisting of characters from {W, A, S, D}, representing the move commands for each second. For a snake of length at least 2, the initial movement direction is determined by the vector from the first body segment to the head. For a snake of length 1, no reversal check is performed.

outputFormat

Output the final grid configuration after simulating the snake movement for T seconds (or until the snake dies). The grid should consist of n lines, each with m characters. If the snake is alive, its head is represented by @ and its body by #. If the snake has died, all cells that were part of the snake become food (i.e. &).

sample

5 6 4
......
......
.@#...
......
......
DDDD

......
......
.&&...
......
......