INK

INK is a platformer puzzle game where you steer a white square past various hazards to reach the goal. Each time the white square jumps, it scatters ink of a color. When the ink hits a transparent obstacle, the obstacle is dyed. After that, the player can see the dyed obstacle.

A stage is an $N \times N$ grid. $(y, x)$ is the cell in row $y$ and column $x$. Each cell is either empty or an obstacle. The player enters $K$ commands in total to steer the square. The commands are:

• Move commands: the uppercase letters U, D, L, R, which move the square one cell up, down, left, or right. If the move takes the square outside the stage or onto an obstacle, the command is ignored.
• Ink command: the lowercase letter j. It increases the square's ink amount by 1. The ink amount is 0 at the start.
• Jump command: the uppercase letter J. The square jumps in place and scatters ink. The amount of scattered ink equals the square's current ink amount. Right after the jump, the square's ink amount becomes 0.

When ink of color $c_i$ and amount $m_i$ is scattered at $(y_i, x_i)$, every obstacle cell $(a, b)$ with $|y_i-a|+|x_i-b| \le m_i$ is painted $c_i$. If an obstacle is already painted a different color, it is repainted with the color of the later ink that reaches it.

The ink color depends on the jump count and the ink string. The ink string is an uppercase string of length $I$. The color of the $(t \times I + d)$-th jump is the $d$-th character of the ink string, where $t$ is a non-negative integer and $1 \le d \le I$. For example, the 1st jump uses the 1st character, the 2nd jump uses the 2nd character, the $I$-th jump uses the $I$-th character, the $(I+1)$-th jump uses the 1st character, and the $(I+2)$-th jump uses the 2nd character.

The first line has three integers $I$, $N$, and $K$, separated by spaces. ($1 \le I, N, K \le 100$)

The second line is the ink string.

The next $N$ lines give the $N \times N$ stage. @ is the square, . is an empty cell, and # is an obstacle. There is exactly one square.

The last line contains the $K$ commands with no spaces between them.

Print the final stage as $N$ lines of $N$ characters each.

Print @ for the square, . for an empty cell, # for an undyed obstacle, and the uppercase letter of the ink color for a dyed obstacle.