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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class A295 {

    void solve(){
        int n = readInt();
        int m = readInt();
        int k = readInt();
        long[] a = new long[n];
        for(int i = 0;i<n;i++){
            a[i] = readInt();
        }

        int[][] b = new int[3][m];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<3;j++){
                if(j != 2) b[j][i] = readInt() - 1;
                else b[j][i] = readInt();
            }
        }

        long[] plus = new long[m];

        long[] segments = new long[m];

        long now = 0;
        for(int i = 0;i<k;i++){
            int left = readInt() - 1;
            int right = readInt() - 1;
            segments[left]++;
            if(right + 1 < m) segments[right + 1]--;
        }

        for(int i = 0;i<m;i++){
            now += segments[i];
            plus[i] = now;
        }

        segments = new long[n];
        for(int i = 0;i<m;i++){
            int left = b[0][i];
            int right = b[1][i];
            long d = b[2][i];
            segments[left] += plus[i] * d;
            if(right + 1 < n) segments[right + 1] -= plus[i] * d;
        }

        now = 0;
        for(int i = 0;i<n;i++){
            now += segments[i];
            a[i] += now;
        }

        for(long i : a) out.print(i + " ");
    }

    public static void main(String[] args) {
        new A295().run();
    }

    void run(){
        init();
        solve();
        out.close();
    }

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok = new StringTokenizer("");

    void init(){
        in = new BufferedReader(new InputStreamReader(System.in));
        out  = new PrintWriter(System.out);
    }

    String readLine(){
        try{
            return in.readLine();
        }catch(Exception ex){
            throw new RuntimeException(ex);
        }
    }
    String readString(){
        while(!tok.hasMoreTokens()){
            String nextLine = readLine();
            if(nextLine == null) return null;
            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt(){
        return Integer.parseInt(readString());
    }

    long readLong(){
        return Long.parseLong(readString());
    }

    double readDouble(){
        return Double.parseDouble(readString());
    }
}
