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 compprog;

import java.util.ArrayList;
import java.util.Scanner;

public class greg {
	public static class xd {
		int one;
		int two;
		int three;
		public xd(int q, int w, int e){
			one = q;
			two = w;
			three = e;
		}
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		  int n = in.nextInt();
		  int m = in.nextInt();
		  int k = in.nextInt();
		  int l,r,d,x,y;
		  ArrayList<Long> arr = new ArrayList<Long>(n);
		  ArrayList<xd> operations = new ArrayList<xd>(m);
		  ArrayList<Integer> query_count = new ArrayList<Integer>(m+1);
		  ArrayList<Long> add_count = new ArrayList<Long>(n+1);
		  for(int i=0;i<n;i++){
		    arr.add(in.nextLong());
		  }
		  for(int i=0;i<m;i++){
			l = in.nextInt();
			r = in.nextInt();
			d = in.nextInt();
		    operations.add(new xd(l-1,r-1,d));
		  }
		  for(int i=0;i<m+1;i++){
				query_count.add(0);
		  }
		  for(int i=0;i<n+1;i++){
				add_count.add(0L);
		  }
		  for(int i=0;i<k;i++){
			  x = in.nextInt();
			  y = in.nextInt();
		    --x;
		    --y;
		    query_count.set(x, query_count.get(x)+1);
		    query_count.set(y+1, query_count.get(y+1)-1);
		  }
		  
		  long total = 0;
		  for(int i=0;i<m;i++){
		    total += query_count.get(i);
		    if(total > 0){
		    	add_count.set(operations.get(i).one, add_count.get(operations.get(i).one)+(operations.get(i).three*total));
		    	add_count.set(operations.get(i).two+1, add_count.get(operations.get(i).two+1)+(-1*operations.get(i).three*total));
		    }
		  }
		  total = 0;
		  for(int i=0;i<n;i++){
		    total += add_count.get(i);;
		    System.out.print(arr.get(i)+total + " ");
		  }
	}
}
