题目描述

给定一个长度为 $n$ 的数组 $a$，以及编号为 $1$ 到 $m$ 的修改指令。第 $i$ 条指令包含三个整数 $l_i,r_i,d_i$，执行它会让数组中位置 $l_i$ 到 $r_i$ 的元素都增加 $d_i$。

另有 $q$ 个执行批次。每个批次给出两个编号 $x,y$，表示把编号为 $x,x+1,\ldots,y$ 的每条指令各执行一次。某条指令如果属于多个批次，就会被重复执行。

所有指令都只进行加法，不会根据数组当前值改变行为。请输出执行完全部批次后的数组。

输入格式

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

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，第 $i$ 行三个整数 $l_i,r_i,d_i$，描述第 $i$ 条指令。

接下来 $q$ 行，每行两个整数 $x,y$，描述一个执行批次。

输出格式

输出一行 $n$ 个整数，依次表示最终数组，相邻两个数之间用一个空格分隔。

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

3 6 7 9 10

1 1 3
1000000000
1 1 1000000
1 1
1 1
1 1

1003000000

样例 1 解释

三条指令分别执行 $1,2,1$ 次，最终数组为 $3,6,7,9,10$。

样例 2 解释

唯一指令被执行三次，最终值为 $1000000000+3\times1000000=1003000000$。

数据范围与提示

对于所有测试点：$1\le n,m,q\le200000$，$0\le a_i\le10^9$，$0\le d_i\le10^6$。

每条指令满足 $1\le l_i\le r_i\le n$；每个批次满足 $1\le x\le y\le m$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$n,m,q\le30$
6—10	$n,m,q\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。