Giải bài trực tuyến

ktuan usually plays a marble game in a square table of NxN cells. The game proceeds as the following:

• Initially, ktuan puts K obstacles into K cells of the table.
• After that, ktuan makes Q turns. At the i^th turn, ktuan flicks D_i marbles from the outside of the board into one of the 4 sides of the board. The size of each marble fits perfectly into one cell.  The marble goes through the cells in the same row/column until it goes out of the board or it meets an obstacle or another marble. If there is an obstacle or another marble at the first position then the marble will not be placed on the board.
• After each turn, ktuan records the total number of cells that the marbles in that turn passing through.

Write a program that simulates the game and for each turn, print the total number of cells that the marbles in that turn passing through.

Input

• The first line contains three integers N, K, Q.
• Each line in the next K lines contains a pair (u, v) representing the coordinates (row, column) of an obstacle.
• Each line in the next Q lines contains 4 values c, D, u, v. The character c could be 'L', 'R', 'T', or 'B' depending on whether the marbles go from the left, right, top, or bottom of the board. (u, v) represents the initial coordinates of the marbles and it should be a boundary cell (corresponding to c). D is the number of marbles in the current turn.

Output

• For each turn, print the total number of cells that the marbles passing through.

Example

Input 
5 1 3
3 3
L 2 3 1
T 1 1 1
B 5 5 5

Output
3
2
25

Output details

• The first marble of the first turn will go through the two cells (3, 1) and (3, 2) before facing an obstacle at (3, 3).
• The next marble of the first turn will go through the cell (3, 1) before facing another marble at (3, 2). Thus, the total number of cells passed through is 3.
• The first marble of the second turn will pass through the two cells (1, 1) and (2, 1) before facing a marble at the cell (3, 1).
• Each marble of the last turn will go out of the board as it doesn't tough obstacle or another marble. Thus, each marble will pass through 5 cells.

Constraints

• N ≤ 50000, K ≤ 10, Q ≤ 100000
• In 1/3 of the test cases, N and Q do not exceed 1000.