P9804 [POI 2022/2023 R1] kol

This problem is translated from [POI2022~2023R1 kol](https://sio2.mimuw.edu.pl/c/oi30-1/p/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.

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.

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`).

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

The subtasks are as follows: | Subtask ID | Special Property | Points | | :----------: | :----------: | :----------: | | $1$ | $m \leq 300$ and $p,n \leq 2000$ | $20$ | | $2$ | $m \leq 800$ and $p,n \leq 50000$ | $20$ | | $3$ | $c_i=0$ | $20$ | | $4$ | No additional constraints | $40$ | In this problem, subtask $0$ is the sample. Translated by ChatGPT 5