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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Pavel Chuprikov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskA solver = new TaskA();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskA {

    class Fenvick {
        long[] a;

        Fenvick(int n) {
            a = new long[n];
        }

        void addOne(int l, int d) {
            add(l, d);
            if (l > 0)
                add(l - 1, -d);
        }

        void add(int l, long d) {
            for (int idx = l; idx >= 0; idx = ((idx + 1) & idx) - 1) {
                a[idx] += d;
            }
        }

        long get(int l) {
            long res = 0;
            for (int idx = l; idx < a.length; idx = (idx + 1) | idx) {
                res += a[idx];
            }
            return res;
        }
    }

    public void solve(int testNumber, FastScanner in, PrintWriter out) {
        int n = in.nextInt();

        int m = in.nextInt();
        int k = in.nextInt();


        Fenvick res = new Fenvick(n);
        for (int i = 0; i < n; i++) {
            res.addOne(i, in.nextInt());
        }

        int[] l = new int[m];
        int[] r = new int[m];
        int[] d = new int[m];
        for (int i = 0; i < m; i++)
        {
            l[i] = in.nextInt() - 1;
            r[i] = in.nextInt() - 1;
            d[i] = in.nextInt();
        }

        Fenvick opers = new Fenvick(m);
        for (int i = 0; i < k; i++)
        {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            opers.add(y, 1);
            if (x > 0)
                opers.add(x - 1, -1);
        }

        int[] opArr = new int[m];
        for (int i = 0; i < m; i++) {
            opArr[i] = (int)opers.get(i);
        }

        for (int i = 0; i < m; i++) {
            res.add(r[i], 1L * d[i] * opArr[i]);
            if (l[i] > 0)
                res.add(l[i] - 1, -d[i] * 1L * opArr[i]);
        }

        for (int i = 0; i < n; i++) {
            out.print(res.get(i) + " ");
        }
        out.println();
    }
}

class FastScanner {
    private BufferedReader br;
    private StringTokenizer st;

    public FastScanner(InputStream in) {
        this.br = new BufferedReader(new InputStreamReader(in));
    }

    public boolean hasNext() {
        try {
            while (st == null || !st.hasMoreTokens()) {
                final String nextLine = br.readLine();
                if (nextLine == null) {
                    return false;
                } else {
                    st = new StringTokenizer(nextLine);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();  //To change body of catch statement use File | Settings | File Templates.
        }
        return true;
    }

    public String next() {
        return hasNext() ? st.nextToken() : null;
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}

