​ 给定一个长度为 $n$ 数组 A，执行以下操作 $m$ 次：

​ 选择一段区间 $[l,r]$，将区间中所有的数加上整数 $x$。

​ 操作完成后回答 $k$ 个问题：

​ 每个问题给定一段区间 $[l,r]$，输出区间中所有数的和。

输入格式

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

​ 接下来一行 $n$ 个数，表示数组 $A$。

​ 接下来 $m$ 行，每行输入三个整数 $l,r,x$。

​ 接下来 $k$ 行，每行输入两个整数 $l,r$。

输出格式

​ 输出 $k$ 行，每行一个数表示对应问题的和。

样例输入

10 1 1
1 2 3 4 5 6 7 8 9 10
5 8 1
8 9

样例输出

18

数据规模

​ 对于全部数据，保证 $1\leq n \leq 2 \times 10^5$，$1\leq m,k \leq 10^5$，$|x|\leq 10^5$。