Alice is now tired of teaching Ave and wanted to trick Ave with some operations on an array. So, Alice gives Ave an array of length n. Then she gives m operations which have 3 integers l, r, a. So, in these operations Ave would increase the array elements from l to r indices by a.
Also, Alice would give q queries. These queries would have two integers x, y. So, Ave would perform x, x+1,... y operations.
So, Ave would have to tell Alice the array elements after performing this operations.
Input:
First line would contain n, m, q.
Second line would contain n space-separated array elements.
Next m lines would contain 3 space-separated integers l, r, a.
Next q lines would contain x, y.
Output:
There would be n space-separated integers containing array elements after performing the operations.
Constraints:
0 < n, m, q <= 105
1 <= l <= r <= n
0 <= a <= 105
1 <= x <= y <= m
