P9804 [POI 2022/2023 R1] kol

题目译自 [POI2022~2023R1 kol](https://sio2.mimuw.edu.pl/c/oi30-1/p/kol/)。 注意：原题时限为 32s，为避免卡评测，此题时限改为 3s。

你在一个 $m \times m$ 的棋盘上玩贪吃蛇游戏，已知原本蛇长度为 $1$，内容为 `0`，在 $(1,1)$ 处，棋盘上存在 $p$ 个“食物点”，当一条蛇吃了一个“食物点”时，它将会在其头部增加一个食物点对应数值的部分，下图可以更清楚的演示吃食物的过程（红色数字为蛇身）：  现在你进行了 $n$ 个操作，存在移动操作（上下左右）和查询操作（询问一个点是否被蛇覆盖），请编写一个程序求出它。

第一行三个整数 $m$，$p$，$n \ (1 \leq m \leq 2000$，$1 \leq p \leq \min(m^2 - 1, 10^6)$，$1 \leq n \leq 10^6)$。 接下来 $p$ 行，每行三个整数 $w_i$，$k_i$，$c_i \ (1 \leq w_i,k_i \leq m$，$0 \leq c_i \leq m^2-1)$，表示坐标 $(w_i,k_i)$ 的点是一个存在食物为 $c_i$ 的食物点。 然后 $n$ 行，每行先是一个字符。 - 如果该字符为 `Z`，则紧接着后面两个左边 $w_j',k_j'$，表示询问 $(w_j',k_j')$ 的地方是否存在蛇身，不存在输出 $-1$，存在输出对应的内容（数值）。 - 否则，按照对应顺序移动：上（`G`）、下（`D`）、左（`L`）或右（`P`）。

对应字符为 `Z` 的，输出对应的输出。

子任务分配如下： | 子任务编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $m \leq 300$ 且 $p,n \leq 2000$ | $20$ | | $2$ | $m \leq 800$ 且 $p,n \leq 50000$ | $20$ | | $3$ | $c_i=0$ | $20$ | | $4$ | 无附加限制 | $40$ | 本题中，子任务 $0$ 为样例。