题目背景

题目译自 POI2022~2023R1 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 的，输出对应的输出。

6 5 14
1 3 1
5 1 5
2 3 2
3 4 1
3 5 3
Z 1 1
Z 1 2
P
P
D
D
P
Z 3 5
P
Z 3 5
D
Z 3 5
L
Z 3 5

0
-1
-1
3
1
2

提示

子任务分配如下：

本题中，子任务 $0$ 为样例。