27168번 - 브루마블

문제

《브루마블(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$개의 줄에 작업에 대한 정보가 한 줄에 하나씩 주어집니다. $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$
• 점수 계산 작업이 적어도 하나 존재합니다.
• 각 칸의 화살표가 가리키는 방향에 항상 칸이 존재합니다.

힌트