题目描述

ak_coding在学习完差分数组的区间修改，单点查询后，突发奇想，如果想实现一个区间修改，区间查询的算法，有没有什么方式可以帮助他快速实现呢，他希望你可以帮帮他。

输入描述

第一行，为三个正整数 $n,m,q(1\le n,m,q\le 10^5)$ 。分别表示数组长度，区间修改，区间查询的次数

第二行，为 $n$ 个正整数 $a_1,a_2, \cdots ,a_n(1\le a_i\le 10^5)$

接下来 $m$ 行，每行为三个正整数 $l_i,r_i,c_i$ ，表示对区间$[l_i,r_i]$中所有的数添加元素$c_i$，其中$1\le l_i\le r_i\le n,1\le c_i\le 10^5$

接下来$q$行，每行为两个正整数 $l_i,r_i$ ，表示查询区间$[l_i,r_i]$中所有的元素和，其中$1\le l_i\le r_i\le n$

输出描述

共 $q$ 行。

第 $i$ 行为第 $i$ 组答案的询问。

样例

输入

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

输出

34
22