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.

Input

The first line contains integers $*n*$, $*m*$, $*k*$ $(1 ≤ *n*, *m*, *k* ≤ 10^{5})$. The second line contains $*n*$ integers: $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(0 ≤ *a*_{*i*} ≤ 10^{5})$ — 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^{5})$.

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*_{1}, *a*_{2}, ..., *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.