Problem Description

Zhuanzhuan has an operation sequence of length $n$, $(l_i, r_i, v_i)$.

Now there are $q$ queries $(L, R)$.

For each query, you initially have a sequence $c$ of length $m$, with all initial values equal to $0$.

Now we execute, in order, the operations corresponding to items $L, L+1, L+2, \cdots, R$ of the operation sequence.

Each operation sets $c_{l_i}$ through $c_{r_i}$ to $v_i$.

For each query, output the sum of all numbers in the entire sequence $c$ after all operations finish.

Queries are independent of each other.

Input Format

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

Lines $2$ to $n+1$ each contain three positive integers. Line $i+1$ gives $l_i, r_i, v_i$.

The next $q$ lines each contain two positive integers, describing one query $L, R$.

Output Format

Output $q$ lines, each containing one positive integer, the answer to the query.

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

8
14
4

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

124
98
124
86
59
80
28
124
80
127

Hint

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

For $100\%$ of the testdata, it holds that:

$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 L \le R \le n$.

Translated by ChatGPT 5