题目描述

给定一个长度为 $n$ 的整数序列 $a$。

首先进行 $m$ 次区间修改。每次修改给出 $l,r,x$，表示把 $a_l\sim a_r$ 都增加 $x$。

所有修改完成后，再进行 $q$ 次区间查询。每次查询给出 $l,r$，要求输出最终序列中 $a_l+a_{l+1}+\cdots+a_r$ 的值。

注意：所有修改一定发生在所有查询之前。

输入格式

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

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行输入三个整数 $l,r,x$，表示一次区间修改。

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

输出格式

对每次查询输出一行答案。

样例

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

24
43
14

数据规模与约定

• $1\le n,m,q\le 2\times 10^5$；
• $|a_i|,|x|\le 10^9$；
• $1\le l\le r\le n$。

答案可能超过 int 范围。