Greg has an array a=a1,a2,...,an and m operations. Each operation looks as: li, ri, di, (1 \le li \le ri \le n). To apply operation i to the array means to increase all array elements with numbers li,li+1,...,ri by value di.

Greg wrote down k queries on a piece of paper. Each query has the following form: xi, yi, (1 \le xi \le yi \le m). That means that one should apply operations with numbers xi,xi+1,...,yi 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 \le n,m,k \le 105). The second line contains n integers: a1,a2,...,an (0 \le ai \le 105) - the initial array.

Next m lines contain operations, the operation number i is written as three integers: li, ri, di, (1 \le li \le ri \le n), (0 \le di \le 105).

Next k lines contain the queries, the query number i is written as two integers: xi, yi, (1 \le xi \le yi \le 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.