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
//package com.example.programmingpractice;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeSet;

import sun.reflect.generics.tree.Tree;

public class CodeforcesNT {

    static String[] sTakeInputs;
    static int sInputPos = 0;
    static BufferedReader sBufferedReader;
    static StringBuilder outputBuilder = new StringBuilder();

    static int[] scanIntArray() throws Exception{
        String[] inputs = sBufferedReader.readLine().trim().split(" ");
        int[] arr = new int[inputs.length];
        for(int i = 0; i<inputs.length; i++) arr[i] = Integer.parseInt(inputs[i]);
        return arr;
    }

    static long[] scanLongArray() throws Exception{
        String[] inputs = sBufferedReader.readLine().trim().split(" ");
        long[] arr = new long[inputs.length];
        for(int i = 0; i<inputs.length; i++) arr[i] = Long.parseLong(inputs[i]);
        return arr;
    }

    static int scanInt() throws Exception{
        return Integer.parseInt(sBufferedReader.readLine().trim());
    }

    static long scanLong() throws Exception{
        return Long.parseLong(sBufferedReader.readLine().trim());
    }

    static int nextInt() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return Integer.parseInt(sTakeInputs[sInputPos++]);
    }

    static long nextLong() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return Long.parseLong(sTakeInputs[sInputPos++]);
    }

    static String nextString() throws Exception {
        if(sInputPos == 0) sTakeInputs = sBufferedReader.readLine().trim().split(" ");
        if(sTakeInputs.length <= sInputPos) {
            sTakeInputs = sBufferedReader.readLine().trim().split(" ");
            sInputPos = 0;
        }
        return sTakeInputs[sInputPos++];
    }

    static void print(int n, char ch) {
        outputBuilder.append(n).append(ch);
    }

    static void print(long n, char ch) {
        outputBuilder.append(n).append(ch);
    }

    static void print(String n, char ch) {
        outputBuilder.append(n).append(ch);
    }

    static void print(double n, char ch) {
        outputBuilder.append(n).append(ch);
    }

    static void print(float n, char ch) {
        outputBuilder.append(n).append(ch);
    }

    static void print(char ch) {
        outputBuilder.append(ch);
    }

    static void printf() {
        System.out.print(outputBuilder);
    }

    static int gcd(int a, int b) {
        if(a%b == 0) return b;
        return gcd(b, a%b);
    }

    static long gcd(long a, long b) {
        if(a%b == 0) return b;
        return gcd(b, a%b);
    }

    static ArrayList<Integer> getPrimes(boolean[] checker) {
        checker[0] = checker[1] = true;
        for(int i = 2; i*i<=checker.length; i++) {
            for(int j = 2; i*j<checker.length; j++) checker[i*j] = true;
        }
        ArrayList<Integer> primes = new ArrayList<>();
        for(int i = 2; i<checker.length; i++) {
            if(!checker[i]) primes.add(i);
        }
        return primes;
    }

    static int getDigitSum(long x) {
        int sum = 0;
        do {
            sum += x%10;
            x/=10;
        }while (x != 0);
        return sum;
    }

    static class Helper {
        int val; int pos; int pi;
        public Helper(int val, int pos) {
            this.val = val;
            this.pos = pos;
        }
    }

    public static int[] radixSort(int[] f){ return radixSort(f, f.length); }
    public static int[] radixSort(int[] f, int n)
    {
        int[] to = new int[n];
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(f[i]&0xffff)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[f[i]&0xffff]++] = f[i];
            int[] d = f; f = to;to = d;
        }
        {
            int[] b = new int[65537];
            for(int i = 0;i < n;i++)b[1+(f[i]>>>16)]++;
            for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
            for(int i = 0;i < n;i++)to[b[f[i]>>>16]++] = f[i];
            int[] d = f; f = to;to = d;
        }
        return f;
    }

    static class Position {
        ArrayList<Integer> poses = new ArrayList<>();
    }

    static int binarySearch(ArrayList<Integer> middle, int left, int right, int x) {
        int mid = (left+right) / 2;
        if(left>=right) return mid;
        if(middle.get(mid)>x) return binarySearch(middle,left, mid-1, x);
        return binarySearch(middle, mid+1, right, x);
    }



    public static void main (String[] args) throws Exception {
        sBufferedReader = new BufferedReader(new InputStreamReader(System.in));
        outputBuilder = new StringBuilder();
        int n = nextInt();
        int m = nextInt();
        int k = nextInt();

        long[] arr = new long[n+1];
        for(int i = 1; i<=n; i++)arr[i] = nextLong();
        int[] left = new int[m+1];
        int[] right = new int[m+1];
        long[] vals = new long[m+1];
        for(int i = 1; i<=m; i++) {
            left[i] = nextInt();
            right[i] = nextInt();
            vals[i] = nextLong();
        }

        long[] ops = new long[m+2];
        for(int i = 0; i<k; i++) {
            int x = nextInt();
            int y = nextInt();
            ops[x]++;
            ops[y+1]--;
        }
        int v = 0;
        for(int i = 1; i<=m; i++) {
            v += ops[i];
            ops[i] = v;
        }

        long[] add = new long[n+2];
        for(int i = 1; i<=m; i++) {
            add[left[i]] += vals[i]*ops[i];
            add[right[i]+1] -= vals[i]*ops[i];
        }

        long val = 0;
        for(int i = 1; i<=n; i++) {
            val += add[i];
            arr[i] += val;
        }

        for(int i = 1; i<n; i++) print(arr[i],' ');
        print(arr[n],'\n');
        printf();
    }
}
