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

public class Main {
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public long nextLong() {
            return Long.parseLong(next());
        }

    }

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);

        OutputStream outputStream = System.out;
        PrintWriter out = new PrintWriter(outputStream);

        new Main().solve(in, out);
        out.close();
    }

    static class Node {
        int value;
        int left;
        int right;
        int diff;
        int max;

        public Node(int value, int left, int right) {
            this.value = value;
            this.left = left;
            this.right = right;
            this.diff = 0;
            this.max = value;
        }

        @Override
        public String toString() {
            return String.valueOf(value + diff * (right - left + 1));
        }
    }

    private static ArrayList<Node> makeSegmentTree(int[] values) {
        int initSize = values.length;
        int expSize = 1;
        while (expSize < initSize) {
            expSize *= 2;
        }

        int treeSize = expSize * 2 - 1;
        int firstElemInd = treeSize - expSize;
        ArrayList<Node> tree = new ArrayList<>(Collections.nCopies(treeSize, null));
        for (int offset = 0; offset < initSize; ++offset) {
            Node node = new Node(values[offset], offset, offset);
            tree.set(firstElemInd + offset, node);
        }

        for (int offset = initSize; offset < expSize; ++offset) {
            Node node = new Node(0, offset, offset);
            tree.set(firstElemInd + offset, node);
        }

        for (int i = firstElemInd - 1; i >= 0; --i) {
            Node lhs = tree.get(i * 2 + 1);
            Node rhs = tree.get(i * 2 + 2);
            Node node = new Node(lhs.value + rhs.value, lhs.left, rhs.right);
            node.max = Math.max(lhs.value, rhs.value);
            tree.set(i, node);
        }

        return tree;
    }

    private static int sumQuery(ArrayList<Node> tree, int from, int to, int ind) {
        Node node = tree.get(ind);
        int left = node.left;
        int right = node.right;

        if (right < from || left > to) {
            return 0;
        } else if (left >= from && right <= to) {
            return node.value + node.diff * (node.right - node.left + 1);
        } else {
            pushDiff(tree, ind);
            int lhs = sumQuery(tree, from, to, ind * 2 + 1);
            int rhs = sumQuery(tree, from, to, ind * 2 + 2);
            updateNode(tree, ind);
            return lhs + rhs;
        }
    }

    private static void pushDiff(ArrayList<Node> tree, int ind) {
        Node node = tree.get(ind);
        if (node.diff != 0) {
            Node lhs = tree.get(ind * 2 + 1);
            Node rhs = tree.get(ind * 2 + 2);
            lhs.diff += node.diff;
            rhs.diff += node.diff;
            node.diff = 0;
        }
    }

    private static void updateNode(ArrayList<Node> tree, int ind) {
        Node node = tree.get(ind);
        Node lhs = tree.get(ind * 2 + 1);
        Node rhs = tree.get(ind * 2 + 2);

        node.value = lhs.value + lhs.diff * (lhs.right - lhs.left + 1);
        node.value += rhs.value + rhs.diff * (rhs.right - rhs.left + 1);

        node.max = lhs.max + lhs.diff;
        node.max = Math.min(node.max, rhs.max + rhs.diff);
    }

    private static void addQuery(ArrayList<Node> tree, int from, int to, int value, int ind) {
        Node node = tree.get(ind);
        int left = node.left;
        int right = node.right;

        if (right < from || left > to) {
        } else if (left >= from && right <= to) {
            node.diff += value;
        } else {
            pushDiff(tree, ind);
            addQuery(tree, from, to, value,ind * 2 + 1);
            addQuery(tree, from, to, value, ind * 2 + 2);
            updateNode(tree, ind);
        }
    }

    private static int maxQuery(ArrayList<Node> tree, int from, int to, int ind) {
        Node node = tree.get(ind);
        int left = node.left;
        int right = node.right;

        if (right < from || left > to) {
            return Integer.MAX_VALUE;
        } else if (left >= from && right <= to) {
            return node.max + node.diff;
        } else {
            pushDiff(tree, ind);
            int lhsMin = maxQuery(tree, from, to, ind * 2 + 1);
            int rhsMin = maxQuery(tree, from, to, ind * 2 + 2);
            updateNode(tree, ind);
            return Math.min(lhsMin, rhsMin);
        }
    }

    public void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();

        long[] values = new long[n];
        for (int i = 0; i < n; ++i) {
            values[i] = in.nextInt();
        }

        int[] from = new int[m];
        int[] to = new int[m];
        long[] val = new long[m];
        for (int i = 0; i < m; ++i) {
            from[i] = in.nextInt();
            to[i] = in.nextInt();
            val[i] = in.nextLong();
        }


        int[] queries = new int[m];
        int x, y;
        for (int i = 0; i < k; ++i) {
            x = in.nextInt();
            y = in.nextInt();
            --x;
            ++queries[x];
            if (y < m) {
                --queries[y];
            }
        }


        for (int i = 1; i < m; ++i) {
            queries[i] += queries[i - 1];
        }

        long[] diff = new long[n];
        for (int i = 0; i < m; ++i) {
            long cnt = queries[i];
            if (cnt > 0) {
                int cFrom = from[i];
                --cFrom;
                int cTo = to[i];
                long cVal = cnt * val[i];

                diff[cFrom] += cVal;
                if (cTo < n) {
                    diff[cTo] -= cVal;
                }
            }
        }

        for (int i = 1; i < n; ++i) {
            diff[i] += diff[i - 1];
        }

        for (int i = 0; i < n; ++i) {
            out.print(values[i] + diff[i]);
            out.print(' ');
        }
        out.println();
    }
}