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


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;
import java.awt.Point;
import java.util.*;
public class A {
	static public void main(String[] args) {
		FastScanner fs = new FastScanner();
			int n =fs.nextInt(),m=fs.nextInt(),k=fs.nextInt();
			long[] core = new long[n];
			for(int i =0;i<n;++i) {
				core[i] = fs.nextLong();
			}
			Pair[] d = new Pair[m];
			Pair[] q = new Pair[k];
			for(int i = 0;i<m;++i) {
				int a = fs.nextInt(),b=fs.nextInt(),c=fs.nextInt();
				d[i] = new Pair(a-1,b-1,c);
			}
			long[] ile2 = new long[m+1];
			for(int i = 0;i<k;++i) {
				int a = fs.nextInt(),b = fs.nextInt();
				q[i] = new Pair(a-1,b-1,0);
			}
			sort(q);
			long sum = 0;
			PriorityQueue<Integer> pq = new PriorityQueue<>();
			int ind = 0;
			for(int i = 0;i<m;++i) {
				for(;ind<k;) {
					if(q[ind].fs<=i) {
						sum++;
						pq.add(q[ind].sd);
						ind++;
					}else break;
				}
				while(!pq.isEmpty()) {
					int cnt = pq.remove();
					if(cnt>=i) {
						pq.add(cnt);
						break;
					}else
						sum--;
				}
				ile2[i]=sum;
			}
			for(int i =0;i<m;++i) {
				d[i].td*=(long)ile2[i];
			}
			sort(d);
			sum = 0;
			ind = 0;
			StringBuilder sb = new StringBuilder();
			long[] ile1 = new long[n+3];
			for(int i = 0;i<n;++i) {
				//System.out.println("dodaw ");
				for(;ind<m;) {
					if(d[ind].fs<=i) {
						sum+=d[ind].td;
						ile1[d[ind].sd+1]-=d[ind].td;
						ind++;
					}else break;
				}
				sum+=ile1[i];
				core[i]+=sum;
				sb.append(core[i]+" ");
			}
			System.out.println(sb);
		
	}
	static class Pair implements Comparable<Pair>{
		int fs;
		int sd;
		long td;
		
		public Pair(int fs, int sd,int td) {
			this.fs = fs;
			this.sd = sd;
			this.td = td;
		}
		
		public int compareTo(Pair o) {
			return Integer.compare(o.fs, fs);
		}
	}
	
	static void sort(Pair[]a) {
		ArrayList<Pair> l = new ArrayList<>();
		for(Pair i : a) {
			l.add(i);
		}
		Collections.sort(l,(c,d)-> {if(c.fs==d.fs)return Integer.compare(c.sd, d.sd);else return Integer.compare(c.fs, d.fs);});
		for(int i= 0;i<a.length;++i) {
			a[i] = l.get(i);
		}
	}
	
	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		String next() {
			while(!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
				return st.nextToken();
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
    }
}
