Background

This problem is translated from POI2022~2023R1 kol.

Note: The original time limit is 32 s. To avoid issues with the judging system, the time limit of this problem is changed to 3 s.

Problem Description

You are playing the Snake game on an $m \times m$ board. Initially, the snake has length $1$, contains 0, and is located at $(1,1)$. There are $p$ “food cells” on the board. When the snake eats a “food cell”, it will extend at its head by a segment corresponding to the value of that food cell. The figure below shows the eating process more clearly (the red numbers are the snake body):

Now you perform $n$ operations, including move operations (up, down, left, right) and query operations (asking whether a cell is covered by the snake). Please write a program to answer them.

Input Format

The first line contains three integers $m$, $p$, $n \ (1 \leq m \leq 2000$, $1 \leq p \leq \min(m^2 - 1, 10^6)$, $1 \leq n \leq 10^6)$.

The next $p$ lines each contain three integers $w_i$, $k_i$, $c_i \ (1 \leq w_i,k_i \leq m$, $0 \leq c_i \leq m^2-1)$, meaning that the cell at coordinate $(w_i,k_i)$ is a food cell with value $c_i$.

Then follow $n$ lines, each starting with a character.

• If the character is Z, then it is followed by two integers $w_j',k_j'$, meaning you query whether there is a snake segment at $(w_j',k_j')$. If not, output $-1$; otherwise, output the corresponding content (value).

• Otherwise, move in the corresponding direction: up (G), down (D), left (L), or right (P).

Output Format

For each operation whose character is Z, output the required answer.

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

Hint

The subtasks are as follows:

In this problem, subtask $0$ is the sample.

Translated by ChatGPT 5