Years ago, Bajtazar played the game Snake on his old mobile phone. Today, he works as a programmer and, out of sentiment, would like to write his own version of the game. Since it is already 2022, Bajtazar would like to add some color to it and move it to a much larger computer screen. Your task is to help him write one of the modules for his game.

Bajtazar named his game Colorful Snake. The game takes place on a square board divided into $m^2$ cells arranged in $m$ rows and $m$ columns. The rows of the board are numbered from $1$ to $m$ from top to bottom, and the columns from $1$ to $m$ from left to right. A colorful snake moves across this board, becoming longer as it consumes snacks placed on the board. The snacks have different colors, and these determine the colors of the individual segments of the snake as it grows. Your module will be responsible for determining the color of the snake segments located on specific cells of the board at given moments in time.

Rules of the game

To simplify the description, all available colors are numbered from $0$ to $m^2 - 1$. At the beginning of the game, the snake is located at the intersection of row $1$ and column $1$, consisting only of a head of color $0$. There are $p$ snacks placed on the board; each occupies one cell and has a specific color. Snack colors may repeat. The player controls the movements of the snake's head so that in each unit of time, the head moves one cell up, down, left, or right. The other segments of the snake follow the head in such a way that the cell occupied by the snake's head before the move is now occupied by the second segment; the cell occupied by the second segment is occupied by the third, and so on. The head never moves toward the cell occupied by the first segment behind the head (i.e., the snake never "reverses"). Furthermore, the head can never move outside the board or onto a cell containing a snake segment – in such a situation, the player loses. When the head moves to a cell occupied by a snack, the snake consumes that snack, causing the snack to disappear from the board and the snake to grow by one segment. This happens in such a way that the snake's head takes on the color of the consumed snack and, after the move, is located in the cell that the snack occupied, while the other segments of the snake do not move during this turn.

For example, consider a $6 \times 6$ board on which five snacks with colors $1, 2, 1, 3, 5$ are placed. In the figure, the positions of the snacks are marked with numbers representing their colors. The initial position of the snake's head is marked with the digit $0$, and the remaining cells are marked with dots. Assume the snake's head makes the following moves in sequence: right, right, down, down, right, right, down, and left. Then, the successive positions of the snake – marked in red on the board – are as follows:

Your module receives a description of the successive moves made by the player and must answer queries about whether a snake segment is present in a given cell of the board at a given moment, and if so, what its color is. You may assume that the snake will not move outside the board or onto a cell occupied by any of its segments during the moves.

Input

The first line of the input contains three integers $m$, $p$, and $n$, representing the length (and width) 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$ ($1 \le w_i, k_i \le m, 0 \le c_i \le m^2 - 1$), indicating that there is one snake snack of color $c_i$ in the cell at row $w_i$ and column $k_i$. All pairs $(w_i, k_i)$ in the input will be distinct and none will be equal to $(1, 1)$, which is the initial position of the snake.

The next $n$ lines contain the description of the commands. A command consists of a single letter G, D, L, P or the letter Z followed by two integers $w'_j, k'_j$. The first four commands indicate the direction in which the snake's head moved: up (G), down (D), left (L), or right (P). The command "Z $w'_j$ $k'_j$" is a query about the color of the snake segment currently located in the cell at row $w'_j$ and column $k'_j$. You may assume that there is at least one such query among the commands.

Output

For each query, output a single integer in the range $[0, m^2 - 1]$ representing the color of the snake segment occupying the cell described in the query at that moment, or $-1$ if no snake segment is present in that cell at that moment.

Examples

Input 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

Output 1

0
-1
-1
3
1
2

Note

The board and the successive moves of the snake are illustrated in the figure above.

Subtasks

In all subtasks, $2 \le m \le 2000$, $1 \le p \le \min(m^2 - 1, 1\,000\,000)$, $1 \le n \le 1\,000\,000$.