Greg has an array a = a 1, a 2, ..., 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.

输入描述:

The first line contains integers n, m, k(1 ≤ n, m, k ≤ 105). The second line contains n integers: a1, a2, ..., an(0 ≤ ai ≤ 105) — the initial array.Next m lines contain operations, the operation number i is written as three integers: li, ri, di, (1 ≤ li ≤ ri ≤ n), (0 ≤ di ≤ 105).Next k lines contain the queries, the query number i is written as two integers: xi, yi, (1 ≤ xi ≤ yi ≤ m).The numbers in the lines are separated by single spaces.

输出描述:

On a single line print n integers a1, a2, ..., an — 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.