Snake Game Simulation

You are given an \(m \times m\) board on which a snake game is played. Initially, the snake has length 1 with content 0 and is located at cell \((1,1)\). There are \(p\) food points on the board; each food point is located at a specific cell and has an associated integer value. When the snake moves to a cell with a food point, it "eats" the food, and a new segment with the corresponding food value is added at the head of the snake (the food point is then removed from the board). Otherwise, when moving, the snake adds a new cell at its head and removes its tail cell, thereby keeping its length unchanged.

You are given \(n\) operations. Each operation is either a move operation or a query operation. The move operations are one of U (up), D (down), L (left), or R (right). The query operation is denoted by a line starting with Q followed by two integers \(x\) and \(y\); for a query, you must output 1 if the snake currently covers the cell \((x,y)\), and 0 otherwise.

inputFormat

The first line contains three integers: \(m\) (the size of the board), \(p\) (the number of food points), and \(n\) (the number of operations).

The next \(p\) lines each contain three integers \(r\), \(c\), and \(v\), representing a food point at row \(r\), column \(c\) with food value \(v\). It is guaranteed that 1 \(\le r, c \le m\).

The next \(n\) lines each describe an operation. A move operation is given as a single character among U, D, L, or R. A query operation is given in the format Q x y, where \(x\) and \(y\) are the coordinates to be queried.

outputFormat

For each query operation, output a line containing a single integer: 1 if the cell is covered by the snake, and 0 otherwise.

sample

5 2 5
2 1 5
1 2 3
R
D
Q 1 1
L
Q 2 1

0
1