Greg has an array a = a₁, a₂, ..., a_n and m operations. Each operation looks as: l_i, r_i, d_i, (1 ≤ l_i ≤ r_i ≤ n). To apply operation i to the array means to increase all array elements with numbers l_i, l_i + 1, ..., r_i by value d_i.

Greg wrote down k queries on a piece of paper. Each query has the following form: x_i, y_i, (1 ≤ x_i ≤ y_i ≤ m). That means that one should apply operations with numbers x_i, x_i + 1, ..., y_i to the array.

Now Greg is wondering, what the array a will be after all the queries are executed. Help Greg.

Input

The first line contains integers n, m, k (1 ≤ n, m, k ≤ 10⁵). The second line contains n integers: a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁵) — the initial array.

Next m lines contain operations, the operation number i is written as three integers: l_i, r_i, d_i, (1 ≤ l_i ≤ r_i ≤ n), (0 ≤ d_i ≤ 10⁵).

Next k lines contain the queries, the query number i is written as two integers: x_i, y_i, (1 ≤ x_i ≤ y_i ≤ m).

The numbers in the lines are separated by single spaces.

Output

On a single line print n integers a₁, a₂, ..., a_n — the array after executing all the queries. Separate the printed numbers by spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.

Greg and Array

Examples