题目描述

Greg 有一个数列 $a\{a_1,a_2,a_3...a_n\}$ 和 $m$ 个操作（不立即执行）。

每个操作将以以下形式给出，如 l r d（$1\le l\le r\le n$）。每个操作的意思是给区间 $[a_{l},a_{r}]$ 中每个数加上 $d$。

Greg 在纸上写下了 $K$ 个问题，每个问题将以以下形式给出，如 x y（$1\le x_\le y_\le m$），这意味着你应该对数组执行第 $x$、第 $x+1$、第 $x+2...$ 第 $y$ 个操作。

现在 Greg 想知道，当操作执行之后数组 $a$ 将会变得怎样。

输入格式

第一行包含三个整数 $n,m,k\ (1\le n,m,k\le 10^5)$。

第二行是原始数列 $a_i$，$0\le a_i\le 10^5$。

接下来 $m$ 行将给出 $m$ 个操作，每行有三个整数，分别为 $l$，$r$，$d$，$1\le l\le r\le n$，$0\le d\le 10^5$。

接下来 $k$ 行包含 $k$ 个问题，每行有两个整数，分别为 $x$，$y$。

输出格式

输出最终数列。

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

9 18 17

1 1 1
1
1 1 1
1 1

2

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

5 18 31 20