브루마블

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

행사는 정확히 한 턴 동안만 진행됩니다. 해당 턴에 특정 격자칸에 있으면 행사에 참여할 수 있습니다. 행사에 참여하는 데 성공하면 점수를 얻으며, 얻는 점수는 행사마다 다릅니다.

게임은 다음 과정으로 진행됩니다.

1. 게임을 시작하기 전에 시작 위치를 정하고 그 위에 말을 놓습니다.
2. 이후 $L$번의 턴을 반복합니다. 한 턴은 다음과 같이 진행됩니다.
   • 먼저 화살표가 가리키는 방향으로 한 칸 이동합니다.
   • 이 칸에서 행사가 열리고 있다면 플레이어는 행사에 해당하는 점수를 얻습니다. 열리고 있는 행사가 여러 개라면 각 행사 점수의 합만큼 점수가 증가합니다.
3. $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$개의 줄에 작업 정보가 한 줄에 하나씩 주어집니다. 형식은 다음과 같습니다.

• $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$)
• 행사 추가 작업이면 $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$이 성립합니다.
• 점수 계산 작업이면 $1 \le X_i \le N$, $1 \le Y_i \le M$이 성립합니다.
• 점수 계산 작업이 적어도 하나 존재합니다.
• 각 칸의 화살표가 가리키는 방향에는 항상 칸이 존재합니다.