题目描述

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

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

输入格式

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

第二行为$\red n$个整数。

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

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

输出格式

输出每一次询问的答案。

样例

输入样例

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

输出样例

5
8

数据范围与提示

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

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