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.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Main
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String n() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int ni() 
        { 
            return Integer.parseInt(n()); 
        } 
  
        long nl() 
        { 
            return Long.parseLong(n()); 
        } 
  
        double nd() 
        { 
            return Double.parseDouble(n()); 
        } 
  
        String nline() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }

   
     public static long[] randomize(long arr[])
    {
        Random rand = new Random();
for (int i = 0; i < arr.length; ++i) {
   int index = rand.nextInt(arr.length - i);
   long tmp = arr[arr.length - 1 - i];
   arr[arr.length - 1 - i] = arr[index];
   arr[index] = tmp;
}

return arr;
    } 

    static long mod = 1000000007;

  
    public static void main (String[] args) throws java.lang.Exception
    {
        FastReader sc = new FastReader();
        StringBuilder fo = new StringBuilder();

        int n = sc.ni();

        long a[]= new long[n];

        int m = sc.ni();
        int k = sc.ni();

        for(int i=0;i<n;i++)
            a[i] = sc.nl();

        long operations[][] = new long[m][3];

        for(int i=0;i<m;i++)
        {
            operations[i][0] = (sc.ni()-1);
            operations[i][1] = (sc.ni()-1);
            operations[i][2] = (sc.ni());
               
        }

        long count[] = new long[m];

        for(int i=0;i<k;i++)
        {
            int from = sc.ni()-1;
            int to =sc.ni()-1;
            count[(int)from]++;
            if(to+1<m)
            count[(int)to+1]--;
        }

        for(int i=1;i<m;i++)
            count[i] = count[i-1]+count[i];

        
        long add[] =new long[n];
        for(int i=0;i<m;i++)
        {
            long from = operations[i][0];
            long to = operations[i][1];
            long cost = operations[i][2] * count[i];

            add[(int)from] = add[(int)from] + cost;
            if(to+1<n)
                add[(int)to+1] = add[(int)to+1] - cost;
        }

        for(int i=1;i<n;i++)
            add[i] = add[i-1]+add[i];
        
        for(int i=0;i<n;i++)
            fo.append(a[i] + add[i]+" ");


        System.out.println(fo);
        
    }
    
    
    
    
}
