Greg and array

Greg has an array of $n$ numbers and $m$ operations. Operation $i$ is $(l_i, r_i, d_i)$: $d_i$ is added to each of the elements $a_{l_i}, \ldots, a_{r_i}$.

Then $k$ queries $(x, y)$ come: all operations with numbers from $x$ to $y$ must be applied. Queries are applied one after another, and an operation may be applied several times. Print the array after all queries.

The first line contains $n$, $m$, $k$ ($1 \le n, m, k \le 10^5$). The second line contains $n$ integers ($0 \le a_i \le 10^5$). The next $m$ lines contain $l_i$, $r_i$, $d_i$ ($1 \le l_i \le r_i \le n$, $0 \le d_i \le 10^5$). The next $k$ lines contain $x$ and $y$ ($1 \le x \le y \le m$).

A single line with $n$ numbers — the final array.

A two-level difference array. First find from the queries how many times every operation is applied: $c_x \mathrel{+}= 1$, $c_{y+1} \mathrel{-}= 1$ and prefix sums. Then operation $i$ adds $c_i \cdot d_i$ to the array — write that with a difference array too and take prefix sums at the end. Everything is $O(n + m + k)$.

Values reach $10^{15}$ — a 64-bit type is needed. In the first example the answer is 9 18 17.

Source: Codeforces, problem 295A.