Greg has an array a = a1, a2, ..., an and m operations. Each operation looks as: li, ri, di, (1 ≤ li ≤ ri ≤ 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 ≤ xi ≤ yi ≤ 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.

Input

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.

Output

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.

Examples

Input

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3


Output

9 18 17


Input

1 1 1
1
1 1 1
1 1


Output

2


Input

4 3 6
1 2 3 4
1 2 1
2 3 2
3 4 4
1 2
1 3
2 3
1 2
1 3
2 3


Output

5 18 31 20
import java.io.*;
import java.util.*;
public class j
{
public static void main(String a[])throws IOException
{
BufferedReader b=new BufferedReader(new InputStreamReader(System.in));
int l1=0,r1=0,incr=0,l=0,r=0,i=0,n=0,m=0,k=0;
String s;
s=b.readLine();
StringTokenizer c=new StringTokenizer(s);
n=Integer.parseInt(c.nextToken());
m=Integer.parseInt(c.nextToken());
k=Integer.parseInt(c.nextToken());
int d[]=new int[n];
long h[]=new long[n];
long p[]=new long[n];
int e[]=new int[m];
String g[]=new String[m];
int f[]=new int[m];
e[0]=0;
f[0]=0;
s=b.readLine();
StringTokenizer z=new StringTokenizer(s);
for(i=0;i<n;i++)
d[i]=Integer.parseInt(z.nextToken());
for(i=0;i<m;i++)
{
g[i]=b.readLine();
}
for(i=0;i<k;i++)
{
s=b.readLine();
StringTokenizer x=new StringTokenizer(s);
l1=Integer.parseInt(x.nextToken());
r1=Integer.parseInt(x.nextToken());
e[l1-1]++;
if(r1<m)
e[r1]--;
}
f[0]=e[0];
for(i=1;i<m;i++)
f[i]=e[i]+f[i-1];
for(i=0;i<m;i++)
{
StringTokenizer y=new StringTokenizer(g[i]);
l=Integer.parseInt(y.nextToken());
r=Integer.parseInt(y.nextToken());
incr=Integer.parseInt(y.nextToken());
h[l-1]+=(long)f[i]*incr;
if(r<n)
h[r]-=(long)f[i]*incr;
}
p[0]=h[0];
for(i=1;i<n;i++)
p[i]=p[i-1]+h[i];
for(i=0;i<n;i++)
System.out.print((p[i]+d[i])+" ");
}
}