Brue Marble

Brue Marble is a game where you move the hero Brue across a board so that Brue can join events held at different places on the board. The board is a grid of $N$ rows and $M$ columns. Each cell has an arrow pointing in one of 8 directions: up, down, left, right, or one of the four diagonals. The cell in the direction each arrow points to always exists.

An event lasts for exactly one turn. If the player is on the event's cell during that turn, the player can join the event and earn points. The points for each event are set by that event.

The game runs as follows.

1. Before the game starts, choose a starting cell and place the piece on it.
2. Repeat the following turn $L$ times. Each turn works like this:
   • First, move one cell in the direction the arrow on the current cell points.
   • If an event is open on the new cell, the player earns the points for that event. If several events are open there, the player earns the sum of their points.
3. After $L$ turns, compute the final score.

Most of the game is finished, but the events have not been decided yet. You are a beta tester and need to simulate the game to check whether its balance is right. You must compute the final score when a given cell is the starting cell. Events may be added during the process, and you must reflect each addition. No events are scheduled at the start.

You must handle the following two kinds of tasks. Write cell $(i, j)$ for row $i$ and column $j$.

• Add an event: add an event that opens at cell $(X_i, Y_i)$ during turn $T_i$. Joining this event earns $W_i$ points.
• Compute the score: compute the final score when the piece starts at cell $(X_i, Y_i)$.

The first line contains two integers $N$ and $M$, the size of the grid, and two integers $L$ and $Q$, the number of turns and the number of tasks.

The next $N$ lines describe the arrows. Line $i$ contains $M$ characters, and character $A_{i, j}$ is the arrow in row $i$, column $j$. Row numbers increase from top to bottom and column numbers increase from left to right. The characters mean the following directions.

• Q: up-left
• W: up
• E: up-right
• D: right
• C: down-right
• X: down
• Z: down-left
• A: left

The next $Q$ lines each describe one task, in one of these formats.

• $1 \ T_i \ X_i \ Y_i \ W_i$: add an event that opens at $(X_i, Y_i)$ during turn $T_i$. Joining it earns $W_i$ points.
• $2 \ X_i \ Y_i$: compute the final score when the piece starts at $(X_i, Y_i)$.

For each score computation task, print the final score on its own line.

• $2 \le N, M \le 500$
• $1 \le L \le 10^9$
• $1 \le Q \le 250\,000$
• $A_{i, j} \in \{\text{Q}, \text{W}, \text{E}, \text{D}, \text{C}, \text{X}, \text{Z}, \text{A}\}$ for $1 \le i \le N$ and $1 \le j \le M$
• For an add-event task: $1 \le T_i \le L$, $1 \le X_i \le N$, $1 \le Y_i \le M$, $1 \le W_i \le 10^3$.
• For a score computation task: $1 \le X_i \le N$ and $1 \le Y_i \le M$.
• There is at least one score computation task.
• Every arrow points to a cell that exists on the board.