Bajtazar 多年前曾在他的旧手机上玩过贪吃蛇游戏。如今他成为了一名程序员，出于怀旧，他想编写一个自己的版本。由于现在已经是 2022 年，Bajtazar 想在游戏中加入一些色彩，并将其移植到更大的电脑屏幕上。你的任务是帮助他编写游戏的一个模块。

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 \le w_i, k_i \le m, 0 \le c_i \le 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$ 列的蛇身部分的颜色。你可以假设指令中至少包含一个这样的查询。

输出格式

对于每个查询，输出一行，包含一个范围在 $[0, m^2 - 1]$ 内的整数，表示查询时刻该格子中蛇身部分的颜色；如果该时刻该格子中没有蛇身，则输出 $-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

说明

样例解释：棋盘和蛇的连续移动如上图所示。

子任务

在所有子任务中，满足 $2 \le m \le 2000, 1 \le p \le \min(m^2 - 1, 1\,000\,000), 1 \le n \le 1\,000\,000$。