【题目描述】

小蓝负责整理集训期间的值日安排。

集训一共有 $n$ 天，第 $i$ 天原本的基础工作量为 $a_i$。

接下来老师给出了 $m$ 次安排，每次安排形如 $l,r,x$，表示第 $l$ 天到第 $r$ 天每天都要额外增加 $x$ 的工作量。

所有安排确定后，小蓝还要回答 $q$ 次询问。每次询问给出 $l,r$，你需要求出第 $l$ 天到第 $r$ 天的最终工作量总和。

---

【输入描述】

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

第二行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来 $m$ 行，每行输入三个整数 $l,r,x$，表示一次安排。

接下来 $q$ 行，每行输入两个整数 $l,r$，表示一次询问。

保证：

• $1\le n,q\le 2\times 10^5$，$0\le m\le 2\times 10^5$；
• $0\le a_i,x\le 10^9$；
• 对于所有安排和询问，均满足 $1\le l\le r\le n$；
• 所有需要输出的答案均不超过 $9\times 10^{18}$。

---

【输出描述】

对于每次询问，输出一行一个整数，表示对应区间内的最终工作量总和。

---

【样例 1】

【样例 1 输入】

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

【样例 1 输出】

49
32
5

【样例 1 解释】

所有安排结束后，$5$ 天的最终工作量依次为 $11,13,14,5,6$。

因此：

• 第 $1$ 天到第 $5$ 天的总工作量为 $49$；
• 第 $2$ 天到第 $4$ 天的总工作量为 $32$；
• 第 $4$ 天到第 $4$ 天的总工作量为 $5$。

---

【样例 2】

【样例 2 输入】

6 3 4
0 5 0 5 0 5
2 2 1000000000
1 6 3
4 6 7
2 2
1 3
4 6
1 6

【样例 2 输出】

1000000008
1000000014
40
1000000054

【样例 2 解释】

所有安排结束后，$6$ 天的最终工作量依次为 $3,1000000008,3,15,10,15$。

按询问区间分别求和即可。

---

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n,m,q\le 1000$。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $m=0$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例仅满足完整数据范围，无额外限制。

---

【数据规模与约定】

测试点编号	分数	特殊性质
1 ~ 3	15	$n,m,q\le 200$
4 ~ 6	20	$m=0$
7 ~ 9		所有安排均满足 $l=r$
10 ~ 12		$n,m,q\le 5000$
13 ~ 15	25	无额外限制

对于 $100\%$ 的数据，满足输入描述中的完整数据范围。

点击下载本题选手目录