题目描述

给定$n$个整数序列${a_1}$,${a_2}$ ... ${a_n}$,然后给定$m$次修改操作，每次修改操作给定三个整数：$l$,$r$,$c$，表示将${a_l}$ 至 ${a_r}$之间的每一个元素都加上$c$。

当所有的修改操作都完成以后，给定$k$次询问，每次询问给定两个整数$l$,$r$，请回答${a_l}$ 至 ${a_r}$之间所有元素的和。

输入格式

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

第二行为$n$个整数。

接下来m行，每行有三个整数：$l$，${r}$,$c$。

接下来k行，每行有两个整数：$l$，${r}$。

输出格式

输出每一次询问的答案。

样例

输入样例

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

输出样例

5
8

数据范围与提示

对所有的数据：${1≤n≤1000000}$，${1<=m,k≤10000}$.

对于序列中任何一个数据、任何一段区域的和都不会超过int的最大表示范围。