Zhuanzhuan has a sequence of operations $(l_i, r_i, v_i)$.

There are $q$ queries, each given by $l$ and $r$.

For each query, you start with a sequence $c$ of length $m$, initialized to all $0$s.

You perform the $r-l+1$ operations from index $l$ to $r$. Each operation assigns the value $v_i$ to the range $c[l_i]$ to $c[r_i]$.

Calculate the sum of all elements in the sequence $c$ after all operations are completed.

Queries are independent of each other.

Input

The first line contains three positive integers $n$, $m$, and $q$.

The next $n$ lines each contain three positive integers, where the $i$-th line (from $2$ to $n+1$) represents $l_i$, $r_i$, and $v_i$.

The following $q$ lines each contain two positive integers, representing a query $l$ and $r$.

Output

Output $q$ lines, each containing a single positive integer representing the answer to the query.

Examples

Input 1

4 5 3
1 4 3
2 3 1
5 5 2
1 2 4
1 2
1 4
2 3

Output 1

8
14
4

Input 2

10 10 10
1 5 20
5 7 7
3 6 8
1 6 20
1 7 14
5 6 5
9 9 18
5 10 5
1 9 6
1 5 19
1 10
5 5
7 10
4 8
1 9
1 6
6 7
7 10
2 6
1 4

Output 2

124
98
124
86
59
80
28
124
80
127

Subtasks

Idea: Ynoi, Solution: Ynoi, Code: Ynoi, Data: Ynoi

For $100\%$ of the data:

$1 \le n, m, q \le 5 \times 10^5$

$1 \le l_i \le r_i \le m$

$0 \le v_i \le 2 \times 10^9$

$1 \le x_i \le y_i \le n$