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.util.Scanner;
import java.util.StringTokenizer;
import java.util.*;

public class Greg_and_Array {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        double nextDouble() {
            return Double.parseDouble(next());
        }

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

    public static void main(String[] args) {
        FastReader sc = new FastReader();
        Integer n = sc.nextInt();
        Integer m = sc.nextInt(); // operations
        Integer k = sc.nextInt(); //    queries

        Integer[] input = new Integer[n];
        Long[] arr = new Long[n + 1];


        for (int i = 0; i < n; i++) {
            input[i] = (sc.nextInt());
            arr[i] = new Long(0);
        }
        arr[n] = new Long(0);

        operation[] o = new operation[m];
        for (int i = 0; i < m; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int d = sc.nextInt();
            o[i] = new operation(l - 1, r - 1, d);
        }
        long q[] = new long[m+1];
        for (int i = 0; i < k; i++) {
            int x = sc.nextInt() - 1;
            int y = sc.nextInt() - 1;
            q[x]++;
            q[y+1]--;
        }
        o[0].edited = q[0] * o[0].d;
        for(int i = 1;i<q.length-1;i++)
        {
            q[i]+=q[i-1];
            //q[i] = q[i]/2 ;
            o[i].edited = q[i] * o[i].d;
        }

        for (int i = 0; i < o.length; i++) {
            arr[o[i].l] += o[i].edited;
            arr[o[i].r + 1] -= o[i].edited;
        }

        System.out.print(arr[0] + input[0] + " ");
        for (int i = 1; i < arr.length - 1; i++) {
            arr[i] += arr[i - 1];
            long res = arr[i] + input[i];
            System.out.print(res + " ");
        }
    }

    static class operation {
        Integer l;
        Integer r;
        Integer d;
        Long edited;

        operation(Integer l, Integer r, Integer d) {
            this.l = l;
            this.r = r;
            this.d = d;
            edited = new Long(0);
        }
    }


}