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.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.StringTokenizer;

/**
 * 295A
 *
 * @author artyom
 */
public class GregAndArray implements Runnable {
    private BufferedReader in;
    private PrintStream out;
    private StringTokenizer tok;

    private void solve() throws IOException {
        int n = nextInt(), m = nextInt(), k = nextInt();
        long[] a = readLongArray(n);
        int[][] ops = readOps(m);
        long[] applied = calcApplied(m, k);
        long[] added = calcAdded(n, ops, applied);
        for (int i = 0; i < n; i++) {
            a[i] += added[i];
        }
        out.println(join(a, " "));
    }

    private int[][] readOps(int m) throws IOException {
        int[][] ops = new int[m][3];
        for (int i = 0; i < m; i++) {
            ops[i][0] = nextInt();
            ops[i][1] = nextInt();
            ops[i][2] = nextInt();
        }
        return ops;
    }

    private long[] calcApplied(int m, int k) throws IOException {
        long[] tmp = new long[m];
        for (int i = 0; i < k; i++) {
            int l = nextInt(), r = nextInt();
            if (l > 1) {
                tmp[l - 2]--;
            }
            tmp[r - 1]++;
        }
        long[] appl = new long[m];
        appl[m - 1] = tmp[m - 1];
        for (int i = m - 2; i >= 0; i--) {
            appl[i] = appl[i + 1] + tmp[i];
        }
        return appl;
    }

    private long[] calcAdded(int n, int[][] ops, long[] applied) {
        long[] tmp = new long[n];
        for (int i = 0; i < ops.length; i++) {
            long val = applied[i] * ops[i][2];
            if (ops[i][0] > 1) {
                tmp[ops[i][0] - 2] -= val;
            }
            tmp[ops[i][1] - 1] += val;
        }
        long[] added = new long[n];
        added[n - 1] = tmp[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            added[i] = added[i + 1] + tmp[i];
        }
        return added;
    }

    private static String join(long[] entries, CharSequence separator) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0, n = entries.length - 1; i <= n; i ++) {
            sb.append(entries[i]);
            if (i < n) {
                sb.append(separator);
            }
        }
        return sb.toString();
    }

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

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = System.out;
            tok = null;
            solve();
            in.close();
        } catch (IOException e) {
            System.exit(0);
        }
    }

    private long[] readLongArray(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextLong();
        }
        return arr;
    }

    private String nextToken() throws IOException {
        while (tok == null || !tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}