Colorful Snake

Years ago, Bajtazar played the Snake game on his old mobile phone. Today he works as a programmer, and out of nostalgia he wants to write his own version. It is 2022, so he wants to add some color and move the game to a much larger computer screen. Your task is to help him write one module of the game.

The game is played on a square board with $m$ rows and $m$ columns, so the board has $m^2$ cells. Rows are numbered 1 to $m$ from top to bottom, and columns are numbered 1 to $m$ from left to right. All colors are numbered from 0 to $m^2-1$.

At the start, a snake made only of its head is in the cell at row 1, column 1. The head has color 0. There are $p$ snacks on the board. Each snack occupies one cell and has a color. Snack colors may repeat.

In each time unit, the player moves the head one cell up, down, left, or right. The rest of the snake follows the head. The cell the head occupied before the move is now occupied by the second segment, the cell of the second segment is taken by the third segment, and so on. The head never moves into the cell of the first segment behind it, so the snake never turns back. The head may not leave the board or enter a cell that holds another segment of the snake. If it does, the player loses.

When the head moves onto a cell with a snack, the snake eats it. The snack disappears from the board and the snake grows by one segment. The head takes the color of the eaten snack and ends the move on that cell. The other segments do not move during that move.

You may assume that the snake never leaves the board and never enters a cell occupied by its own segments.

The first line contains three integers $m$, $p$, and $n$. They are the side length of the board, the number of snacks on the board, and the number of commands to process.

Each of the next $p$ lines contains three integers $w_i$, $k_i$, and $c_i$. This means there is a snack of color $c_i$ in row $w_i$, column $k_i$. Here $1 \le w_i, k_i \le m$ and $0 \le c_i \le m^2-1$. All pairs $(w_i, k_i)$ are distinct and none of them is the starting cell (1, 1).

Each of the next $n$ lines is a command. A command is one of the letters G, D, L, or P, or the letter Z followed by two integers $w'_j$ and $k'_j$. G means the head moved up, D means it moved down, L means it moved left, and P means it moved right. The command Z w' k' asks for the color of the snake segment in row $w'$, column $k'$ at the current moment. You may assume there is at least one such query.

For each query, print one line with one integer. Print the color of the snake segment occupying the queried cell at that moment, as an integer in the range $[0, m^2-1]$. If no segment of the snake occupies that cell at that moment, print -1.