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 java.math.*;
import java.lang.*;

import static java.lang.Math.*;

public class GregAndArray implements Runnable {

    long mod = 1000000000 +7;
    InputReader read = new InputReader(System.in);

    public void run() {
        int n = read.nextInt();
        int m = read.nextInt();
        int k = read.nextInt();

        Node[] arr = new Node[n+2];
        arr[0] = new Node(0, 0);
        for(int i=1;i<n+1;i++){
            arr[i] = new Node(read.nextLong(), 0);
        }
        arr[n+1] = new Node(0, 0);

        Queries[] qArr = new Queries[m+2];
        qArr[0] = new Queries(0, 0, 0);
        for(int i=1;i<m+1;i++){
            qArr[i] = new Queries(read.nextInt(), read.nextInt(), read.nextInt());
        }
        qArr[m+1] = new Queries(0, 0, 0);

        for(int i=0;i<k;i++){
            int l =read.nextInt();
            int r = read.nextInt();
            qArr[l].count++;
            qArr[r+1].count--;
        }

        {
            long temp = 0;
            for(int i=1;i<m+1;i++){
                temp += qArr[i].count;
                qArr[i].d = qArr[i].d*temp;
                arr[(int)qArr[i].l].diff += qArr[i].d;
                arr[(int)qArr[i].r+1].diff -= qArr[i].d;
            }
        }

        {
            long temp =0;
            for(int i=1;i<n+1;i++){
                temp += arr[i].diff;
                System.out.print((arr[i].num+temp) + " ");
            }
        }

    }

    class Node{
        long num = 0;
        long diff = 0;
        Node(long num,long diff){
            this.num = num;
            this.diff = diff;
        }
    }

    class Queries{
        long l,r,d;
        long count = 0;
        Queries(long l,long r,long d){
            this.l = l;
            this.r = r;
            this.d = d;
        }
    }

    public long modAdd(long a, long b) { return (a % mod + b % mod) % mod;}

    public long modSub(long a, long b) { return ((a % mod - b % mod) % mod);}

    public long modMul(long a, long b) { return ((a % mod) * (b % mod)) % mod;}

    public long modDiv(long a, long b) { return ((a % mod) * (binaryExp(b, mod - 2))) % mod;}

    public long modPow(long a) { return a % (mod - 1);}

    public long binaryExp(long a, long pow) {
        a = a % mod;
        if (pow == 0) {
            return 1;
        } else if (pow == 1) {
            return a;
        } else {
            long half = pow / 2;
            long temp = binaryExp(a, half);
            if (pow % 2 == 0) {
                return (temp * temp) % mod;
            } else {
                return ((a % mod) * ((temp * temp) % mod)) % mod;
            }
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new GregAndArray(), "Main", 1 << 27).start();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}