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.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class ladders295a {
    static BufferedReader __in;
    static PrintWriter __out;
    static StringTokenizer input;

    public static void main(String[] args) throws IOException {
        __in = new BufferedReader(new InputStreamReader(System.in));
        __out = new PrintWriter(new OutputStreamWriter(System.out));

        read();
        int n = nextInt(), m = nextInt(), k = nextInt(), op[][] = new int[m][3];
        long cur = 0, diff[] = new long[n + 1];
        read();
        for(int i = 0; i < n; ++i) {
            if(i == 0) {
                cur = diff[i] = nextInt();
            } else {
                cur += (diff[i] = nextInt() - cur);
            }
        }
        // BIT bit = new BIT(diff);
        for(int i = 0; i < m; ++i) {
            read();
            op[i][0] = nextInt() - 1;
            op[i][1] = nextInt();
            op[i][2] = nextInt();
        }
        int[] cntDiff = new int[m + 1];
        for(int i = 0; i < k; ++i) {
            read();
            ++cntDiff[nextInt() - 1];
            --cntDiff[nextInt()];
        }
        long opCnt = 0;
        for(int i = 0; i < m; ++i) {
            opCnt += cntDiff[i];
            diff[op[i][0]] += opCnt * op[i][2];
            diff[op[i][1]] -= opCnt * op[i][2];
        }
        long[] ans = new long[n];
        for(int i = 0; i < n; ++i) {
            if(i == 0) {
                ans[i] = diff[0];
            } else {
                ans[i] = ans[i - 1] + diff[i];
            }
        }
        println(ans);

        close();
    }

    static class BIT {
        int n;
        long bit[];

        BIT(int size) {bit = new long[n = size + 1];}

        BIT(long[] arr) {
            bit = new long[(n = arr.length) + 1];
            for(int i = 0; i < n; ++i) upd(i, arr[i]);
            ++n;
        }

        void upd(int i, long x) {
            ++i;
            while(i < n) {
                bit[i] += x;
                i += i & (-i);
            }
        }

        long sum(int i) {
            long sum = 0;
            while(i > 0) {
                sum += bit[i];
                i -= i & (-i);
            }
            return sum;
        }
    }

    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final long LMAX = 9223372036854775807L;
    static void read() throws IOException {input = new StringTokenizer(__in.readLine());}
    static String readLine() throws IOException {return __in.readLine();}
    static int nextInt() {return Integer.parseInt(input.nextToken());}
    static int readInt() throws IOException {return Integer.parseInt(__in.readLine());}
    static long nextLong() {return Long.parseLong(input.nextToken());}
    static void print(String s) {__out.print(s);}
    static void println(String s) {__out.println(s);}
    static void print(Object o) {__out.print(o);}
    static void println(Object o) {__out.println(o);}
    static void printy() {__out.println("Yes");}
    static void printY() {__out.println("YES");}
    static void printn() {__out.println("No");}
    static void printN() {__out.println("NO");}
    static void printyn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void printYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void println(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), i++); __out.println(a[a.length - 1]);}
    static void println(long... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), i++); __out.println(a[a.length - 1]);}
    static void println() {__out.println();}
    static void close() {__out.close();}
}