Violet is an active comfort seeker and wishes to know the conditions required in order to achieve maximum comfort.

She has already determined the three conditions required in order to achieve a state of maximum comfiness, firstly a peaceful winter night, secondly a cup of hot chocolate and lastly a large window to observe the falling snow.

Violet's window is an $N\times N$ matrix with rows and columns numbered from $0$ to $N-1$. There are $M$ different snowflakes that she observes. Unfortunately, snowflakes don't last forever and will eventually melt. Luckily for you, for each snowflake, she has written down $R$ and $C$, the row and column the snowflake lands on respectively and $L$ and $D$, the time when the snowflake lands and disappears from the window respectively.

In order for Violet to maximize her enjoyment in the future, she has $Q$ queries for you to answer. Queries come in three possible forms:

• R a b t: The number of snowflakes there are located between row $a$ to $b$, inclusive at time $t$.
• C a b t: The number of snowflakes there are located between column $a$ to $b$, inclusive at time $t$.
• V a b c d t: The number of snowflakes there are located between row $a$ to $b$, inclusive or column $c$ to $d$, inclusive at time $t$.

A snowflake that melts at time $t$ is not included in the answer to queries that have the same $t$.

Conversely, a snowflake that lands on the window at time $t$ is included in the answer to queries that have the same $t$, given that it falls within the constraints of the query.

Note: There may be multiple snowflakes within the same grid at a given time but since all snowflakes are unique, they are to be counted separately.

Input

First line: Three integers, $N$ $(1\le N\le 5000)$, the size of the window, $M$ $(1\le M\le {10}^5)$, the number of snowflakes observed and $Q$ $(1\le Q\le {10}^5)$, the number of queries.

Next $M$ lines: $R_i,C_i$ $(0\le R_i,C_i<N)$, the row and column the snowflake lands on, $L_i$ $(1\le L_i<{10}^9)$, the time when it lands, $D_i$ $(L_i<D_i\le {10}^9)$, the time when it disappears.

Next $Q$ lines: $Q$ valid queries.

For all queries: $a,b$ $(0\le a\le b<N)$, $c,d$ $(0\le c\le d<N)$, $t$ $(1\le t\le {10}^9)$

The following additional constraints will apply.

• At least 20% of the marks will have test cases where $N\le 100$, $M\le 100$, $Q\le 100$, $L_i<D_i\le 100$, $t\le {10}^3$.
• At least 40% of the marks will have test cases where $N\le 1000$, $M\le {10}^3$, $Q\le {10}^3$, $L_i<D_i\le {10}^3$, $t\le {10}^5$.
• The remaining marks will have test cases where $N\le 5000$, $M\le {10}^5$, $Q\le {10}^5$, $L_i<D_i\le {10}^9$, $t\le {10}^9$.

Output

Output the answer to each query on its own line.

Sample Input

6 7 3
2 3 3 9
2 4 4 5
4 4 5 10
4 4 2 8
2 3 1 5
4 5 9 10
2 4 7 9
V 2 3 5 5 7
R 3 4 4
C 4 5 4

Sample Output

2
1
2