Greg has an array *a* = *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* operations. Each operation looks as: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*). To apply operation *i* to the array means to increase all array elements with numbers *l*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub> + 1, ..., *r*<sub class="lower-index">*i*</sub> by value *d*<sub class="lower-index">*i*</sub>.

Greg wrote down *k* queries on a piece of paper. Each query has the following form: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*). That means that one should apply operations with numbers *x*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i*</sub> + 1, ..., *y*<sub class="lower-index">*i*</sub> to the array.

Now Greg is wondering, what the array *a* will be after all the queries are executed. Help Greg.
The first line contains integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 10<sup class="upper-index">5</sup>). The second line contains *n* integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>) — the initial array.

Next *m* lines contain operations, the operation number *i* is written as three integers: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*), (0 ≤ *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>).

Next *k* lines contain the queries, the query number *i* is written as two integers: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*).

The numbers in the lines are separated by single spaces.
import sys
input = sys.stdin.readline
n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
oper = []
queries = []

while (m > 0):
    oper.append(tuple(map(int, input().split())))
    m -= 1

while (k > 0):
    queries.append(tuple(map(int, input().split())))
    k -= 1


ap_arr = []
ap_arr.append(arr)
new_arr = arr.copy()
for l,r,d in oper:
    new_arr = new_arr[:l-1] + [i+d for i in new_arr[l-1:r]] + new_arr[r:]
    ap_arr.append(new_arr)


for xi, yi in queries:
    add = [a_i - b_i for a_i, b_i in zip(ap_arr[yi], ap_arr[xi-1])]
    arr = [sum(x) for x in zip(arr,add)]

print(*arr, sep = ' ')


# for xi, yi in queries:
#     for l, r, d in oper:
#         arr[l-1:r] = [i + d for i in arr[l-1:r]]