暂无测试数据。

题目描述

Greg 有一个数列 a：a1, a2, ..., an，以及 m 种操作。每种操作的格式如下：li, ri, di，意思是将a数列中区间 [li, ri]上的元素都加上di。

Greg在纸上写了k个查询。每个查询的格式如下：xi, yi，意思是将编号为 xi, xi+1, ... , yi 的操作都执行一遍。

Greg想知道，如果把 k 个查询都做一遍，最后数列 a 会是神马样子。

输入输出格式

输入格式：

第一行：n, m, k (1 ≤ n, m, k ≤ 10^5)。

第二行：n个整数： a1, a2, ..., an (0 ≤ ai ≤ 10^5) ，表示初始数列。

接下来m行，每行描述一种操作，括三个数字：li, ri, di （1<=li<=ri<=n，0<=di<=10^5）。

接下来k行，每行描述一个查询，包括二个数字：xi, yi （1<=xi<=yi<=m）。

同一行的数字之间只用一个空格分隔。

输出格式：

输出仅一行，包括n个数字，是完成k个查询后的数列a。数字之间用一个空格分隔。

输入输出样例

input
3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3
output
9 18 17

input
1 1 1
1
1 1 1
1 1
output
2

input
4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3
output
5 18 31 20

内存限制 262144 KB
时间限制 1000 ms