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.

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.

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.