题目描述

转转有一个操作序列$(l_i,r_i,v_i)$。

现在，有 $q$ 个询问 $l$,$r$。

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

现在我们从 $l$ 到 $r$ 执行这 $r-l+1$ 个操作。

每个操作是将 $c[l_i]$~$c[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 x_i \le y_i \le n$。