브루마블 | cho.sh

문제

《브루마블(Brue Marble)》은 주인공 브루를 이동시켜 보드판 이곳저곳에서 열리는 행사에 참여시키는 게임입니다. 게임이 진행되는 보드판은 $N$ 행 $M$ 열의 격자판이고, 각 칸에는 상하좌우 또는 대각선 방향의 $8$ 개 방향 중 하나의 방향을 가리키는 화살표가 그려져 있습니다. 화살표가 가리키는 방향에 격자칸이 항상 존재합니다.

보드게임에는 행사라는 시스템이 있습니다. 이 행사는 정확히 한 턴 동안만 진행되며, 해당 턴에 특정한 격자칸에 있을 경우 행사에 참여할 수 있습니다. 행사에 참여하는 데 성공하면 점수를 얻게 됩니다. 얻는 점수는 행사에 따라 다릅니다.

게임은 다음 과정을 통해서 진행됩니다.

게임을 시작하기 전에, 시작 위치를 정하고 그 위에 말을 놓습니다.
이후 $L$ 번의 턴을 반복합니다. 한 번의 턴은 다음과 같이 진행됩니다.
- 먼저 화살표가 가리키는 방향으로 한 칸 이동합니다.
- 만약 현재 이 칸에서 행사가 열리고 있다면, 플레이어는 행사에 해당하는 점수를 얻습니다. 열리고 있는 행사가 여러 개라면, 각각의 행사에 해당하는 점수의 합만큼 점수가 증가합니다.
$L$ 턴이 끝난 뒤, 최종 점수를 계산합니다.

이 게임은 대부분이 완성되어 있지만, 아직 행사와 관련된 정보가 결정되지 않았습니다. 당신은 이 게임의 베타 테스터로, 게임의 밸런스가 잘 맞춰져 있는지를 시뮬레이션해야 합니다. 당신은 특정 지점이 시작 위치일 때의 최종 점수를 구해야 합니다. 단, 중간에 행사와 관련된 정보가 추가될 수 있고, 그때마다 여러분은 추가된 정보를 반영해야 합니다. 초기에 예정된 행사는 없습니다.

당신이 처리해야 하는 작업은 다음 두 가지와 같습니다. $i$ 행 $j$ 열을 $(i, j)$ 와 같이 표기할 때,

행사 추가 작업: $T\_i$ 턴에 $(X\_i, Y\_i)$ 칸에서 열리는 행사를 추가합니다. 이 행사에 참여할 경우 $W\_i$ 의 점수를 얻을 수 있습니다.
점수 계산 작업: $(X\_i, Y\_i)$ 칸에서 시작할 때 얻는 최종 점수를 계산합니다.

입력

첫 번째 줄에 격자의 크기를 나타내는 두 정수 $N$ , $M$ 과 턴의 수 $L$ , 그리고 작업의 횟수 $Q$ 가 주어집니다.

다음 $N$ 개의 줄에는 각 격자 칸 안의 화살표의 상태가 주어집니다. 이들 중 $i$ 번째 줄에는 $M$ 개의 문자가 주어지며, 이들 중 $j$ 번 문자 $A\_{i, j}$ 는 $i$ 행 $j$ 열의 격자칸 안에 있는 화살표의 방향을 나타냅니다. 위에서 아래로 갈수록 행 번호가 증가하고, 왼쪽에서 오른쪽으로 갈수록 열 번호가 증가한다고 할 때, 각 문자가 나타내는 방향은 아래와 같습니다.

Q: 왼쪽 위
W: 위
E: 오른쪽 위
D: 오른쪽
C: 오른쪽 아래
X: 아래
Z: 왼쪽 아래
A: 왼쪽

다음 $Q$ 개의 줄에 작업에 대한 정보가 한 줄에 하나씩 주어집니다. $i$ 번 작업에 대한 정보는 아래와 같은 형식으로 주어집니다.

$1 \ T\_i \ X\_i \ Y\_i \ W\_i$ : $T\_i$ 턴에 $(X\_i, Y\_i)$ 칸에서 열리는 행사를 추가합니다. 이 행사에 참여할 경우 $W\_i$ 의 점수를 얻을 수 있습니다.
$2 \ X\_i \ Y\_i$ : $(X\_i, Y\_i)$ 칸에서 시작할 때 얻는 최종 점수를 계산합니다.

출력

모든 점수 계산 작업에 대해 최종 점수를 계산해 한 줄에 하나씩 출력합니다.

제한

$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}\\} \~ (1 \le i \le N, \~ 1 \le j \le M)$
$i$ 번 작업이 행사 추가 작업일 때, 다음이 성립합니다.
- $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$
$i$ 번 작업이 점수 계산 작업일 때, 다음이 성립합니다.
- $1 \le X\_i \le N$
- $1 \le Y\_i \le M$
점수 계산 작업이 적어도 하나 존재합니다.
각 칸의 화살표가 가리키는 방향에 항상 칸이 존재합니다.