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
from collections import Counter
import math
from typing import NamedTuple


def prefix_sum(prefix_arr):
    for i in range(1, len(prefix_arr)):
        prefix_arr[i] = prefix_arr[i - 1] + prefix_arr[i]


class Operation(NamedTuple):
    l: int
    r: int
    d: int


def main():
    read = sys.stdin.readline
    n, m, k = (int(i) for i in read().split())
    values: list[int] = [int(i) for i in read().split()]
    operations: dict[int, Operation] = {}
    for i in range(m):
        idx = i + 1
        l, r, d = (int(i) for i in read().split())
        operations[idx] = Operation(l, r, d)

    # Compute the number of times each operation needs to be executed
    prefix_operations = [0] * (m + 2)
    for i in range(k):
        x, y = (int(i) for i in read().split())
        prefix_operations[x] += 1
        # Only affect the subrange from x .. y
        prefix_operations[y + 1] -= 1
    prefix_sum(prefix_operations)

    # Compute the number of values to add to the originala rray using the same method
    prefix_result = [0] * (n + 2)
    for i in range(1, len(prefix_operations) - 1):
        operation = operations.get(i)
        change = operation.d * prefix_operations[i]
        prefix_result[operation.l] += change
        prefix_result[operation.r + 1] -= change
    prefix_sum(prefix_result)

    for i in range(n):
        values[i] += prefix_result[i + 1]

    print(' '.join((str(i) for i in values)))


if __name__ == '__main__':
    main()