七彩贪吃蛇

问题描述

多年前，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) 行包含指令的描述。指令由一个字母 G, D, L, P 或者一个字母 Z 和两个整数 (w_j', k_j') 组成。前四个字母表示蛇头移动的方向： 向上（G），向下（D），向左（L），向右（P）。而指令 Z w_j' k_j' 表示查询在当前时刻，第 (w_j') 行第 (k_j') 列的格子上有什么颜色的蛇的部分。保证在指令中至少有一个这样的查询。

输出格式

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

样例输入 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

样例输出 1

0
-1
-1
3
1
2