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 numpy as np


def main():
    n_m_k_list = list(map(int, str(input()).split()))
    n = n_m_k_list[0]
    m = n_m_k_list[1]
    k = n_m_k_list[2]
    input_arr = list(map(int, str(input()).split()))
    operations = []
    freq = {}
    for i in range(m):
        operations.append(tuple(map(int, str(input()).split())))
        freq[i+1] = 0
    queries = []
    for i in range(k):
        queries.append(tuple(map(int, str(input()).split())))
    # create array with zeros
    marker = np.zeros(n, dtype=int)
    # print(marker)
    # make a dict that has frequency of how many times each operation is to be performed
    for query in queries:
        for ops in range(query[0], query[1] + 1):
            freq[ops] += 1
    # for every operation, increment lth index by (d * freq of d), rth index by the former's negation
    # print(freq)
    for i in range(m):
        # print(i)
        marker[operations[i][0] - 1] += (freq[i+1] * operations[i][2])
        if operations[i][1] <= n-1:
            marker[operations[i][1]] -= (freq[i+1] * operations[i][2])
    # find prefix sum for this array - it will give the number to be added to every corresponding element
    prefix_arr = prefix_sum(marker, n)
    # print(prefix_arr)
    for i in range(n):
        input_arr[i] += prefix_arr[i]
        print(input_arr[i], end=' ')


def prefix_sum (given_arr, size):
    prefix = [given_arr[0]]
    for i in range(1, size):
        prefix.append(prefix[i-1] + given_arr[i])
    return prefix


if __name__ == '__main__':
    main()