题目描述

题目译自 XXX Olimpiada Informatyczna – I etap Kolorowy wąż

多年前，Bajtazar 在他的旧手机上玩过一款叫做贪吃蛇的游戏。现在他是一名程序员，出于怀旧，他想写一个自己的版本的这款游戏。而且既然现在已经是 2022 年了，Bajtazar 想给它加入一些色彩，并把它移植到更大的电脑屏幕上。你的任务是帮助他编写他的游戏的一个模块。

他的游戏叫做七彩贪吃蛇。游戏在一个正方形的棋盘上进行，棋盘被分成 $m^{2}$ 个格子，排成 $m$ 行 $m$ 列。棋盘的行从上到下编号为 $1$ 到 $m$，列从左到右编号为 $1$ 到 $m$。在这个棋盘上，有一条彩色的蛇在移动，它会随着吃掉棋盘上的零食而变得越来越长。零食有不同的颜色，它们决定了蛇的各个部分的颜色，当蛇变长时。你的模块要负责确定，在特定的时间点，棋盘上的各个格子上有什么颜色的蛇的部分。

游戏规则： 为了简化描述，我们把所有的颜色从 $0$ 到 $m^{2}-1$ 编号。游戏开始时，在第 $1$ 行第 $1$ 列的格子上，有一条只有头部的蛇，颜色为 $0$。在棋盘上分布着 $p$ 个零食；每个零食占据一个格子，并且有确定的颜色。零食的颜色可以重复。玩家可以控制蛇头的移动，在每个单位时间段内，蛇头可以向上、下、左、右移动一个格子。蛇头后面跟着的是蛇的其他部分，它们的移动方式是：在蛇头移动之前占据的格子，现在被蛇的第二个部分占据；原来被蛇的第二个部分占据的格子，现在被蛇的第三个部分占据，依此类推。蛇头的移动永远不会朝着蛇的第二个部分占据的格子（也就是说，蛇永远不会后退）。另外，蛇头也不能超出棋盘的边界，或者移动到其他被蛇的部分占据的格子上——这种情况下，玩家就输了。当蛇头移动到一个有零食的格子上时，蛇就吃掉了这个零食，零食就会从棋盘上消失，而蛇就会变长一个单位。蛇头的颜色变成了被吃掉的零食的颜色，并且在移动后，蛇头就在原来零食的格子上，而蛇的其他部分在这次移动中不变。

举个例子，考虑一个 $6 \times 6$ 的棋盘，上面有五个颜色分别为 $1,2,1,3,5$ 的零食。在图中，零食的位置用它们的颜色编号表示。蛇头的初始位置用数字 $0$ 表示，其他的格子用点表示。假设蛇头依次向右、右、下、下、右、右、下、左移动。那么蛇的位置（用红色标出）依次如下：

你的程序需要对于给定的玩家的移动指令，回答关于在特定的时间点，特定的格子上有什么颜色的蛇的部分的查询。在执行移动指令的过程中，蛇不会超出棋盘的边界，也不会移动到其他被蛇的部分占据的格子上。

输入格式

第一行包含三个整数 $m, p, n$，分别表示棋盘的边长，棋盘上的零食数，以及要处理的指令数。

接下来的 $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}$ 的零食。保证输入中的所有 $(w_{i}, k_{i})$ 都不相同，也不等于 $(1,1)$（即蛇的初始位置）。

接下来的 $n$ 行包含指令的描述。指令由一个字母 $\texttt{G}, \texttt{D}, \texttt{L}, \texttt{P}$ 或者一个字母 $\texttt{Z}$ 和两个整数 $w_{j}^{\prime}, k_{j}^{\prime}$ 组成。前四个字母表示蛇头移动的方向： 向上（$\texttt{G}$），向下（$\texttt{D}$），向左（$\texttt{L}$），向右（$\texttt{P}$）。而指令 $\texttt{Z}\,w_{j}^{\prime}\,k_{j}^{\prime}$ 表示查询在当前时刻，第 $w_{j}^{\prime}$ 行第 $k_{j}^{\prime}$ 列的格子上有什么颜色的蛇的部分。保证在指令中至少有一个这样的查询。

输出格式

对于每个查询，输出一个整数，表示在当前时刻，查询的格子上的蛇的部分的颜色， 如果查询的格子上没有蛇的部分输出 $-1$。

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

题目描述中的图片展示了棋盘和蛇的移动过程。

样例 2

见附加文件下 [kol1.in](file:kol1.in) 和 [kol1.out](file:kol1.out)。

该样例满足 $m=4, p=15, n=20$，蛇从左到右，从上到下，依次经过所有的格子，尾巴不移动。

样例 3

见附加文件下 [kol2.in](file:kol2.in) 和 [kol2.out](file:kol2.out)。

该样例满足 $m=100, p=4999, n=50000$，蛇按照同样的路线多次经过所有的格子。所有的零食颜色均为 $0$。

样例 4

见附加文件下 [kol3.in](file:kol3.in) 和 [kol3.out](file:kol3.out)。

该样例满足 $m=2000, p=n=10^6$，蛇只在一个小区域内 $\texttt{PDLGPDLGPDLG}$ 反复打转。

数据范围与提示

对于所有的数据，有 $2 \leq m \leq 2000,1 \leq p \leq \min (m^{2}-1,10^6), 1 \leq n \leq 10^6$。

详细子任务附加限制及分值如下表所示。

子任务编号	额外限制	分值
$1$	$m \leq 300, p, n \leq 2000$	$20$
$2$	$m \leq 800, p, n \leq 50000$	$20$
$3$	所有的零食颜色均为 $0$	$20$
$4$	无额外限制	$40$