题目描述

转转有一个长度为 $n$ 的操作序列 $(l_i,r_i,v_i)$。

现在有 $q$ 个询问 $(L,R)$。

对于每次询问，你初始有一个长度为 $m$ 的序列 $c$，初值全是 $0$。

现在我们依次执行操作序列的第 $L,L+1,L+2,\cdots,R$ 项所对应的操作。

每个操作是将序列 $c$ 的第 $l_i$ 项至第 $r_i$ 项赋值为 $v_i$。

询问所有操作结束后整个序列 $c$ 中所有数的和。

询问之间互相独立。

输入格式

第一行三个正整数 $n,m,q$。

第 $2$ 行至第 $n+1$ 行，每行 $3$ 个正整数，第 $i+1$ 行表示 $l_i,r_i,v_i$。

后面 $q$ 行，每行两个正整数，表示一次询问 $L,R$。

输出格式

$q$ 行，每行一个正整数，表示询问的答案。

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

提示

Idea：Ynoi，Solution：Ynoi，Code：Ynoi，Data：Ynoi

对于 $100\%$ 的数据，满足：

$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$。