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 cf10
{
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		int c = in.nextInt();
		ArrayList<Long> arr = new ArrayList<Long>(a);
		ArrayList<Integer> operations = new ArrayList<Integer>(b);
		ArrayList<Integer> query_count = new ArrayList<Integer>(b+1);
		ArrayList<Long> add_count = new ArrayList<Long>(a+1);
		int l = 0;
		int r = 0;
		int d = 0;
		int x = 0;
		int y = 0;
		for(int i = 0; i < a+1; i++)
		{
			if(i < a)
			{
				arr.add(in.nextLong());
			}
			add_count.add(0l);
		}
		for(int i = 0; i < b+1; i++)
		{
			if(i < b)
			{
				l = in.nextInt();
				r = in.nextInt();
				d = in.nextInt();
				operations.add(l-1);
				operations.add(r-1);
				operations.add(d);
			}
			query_count.add(0);
		}
		for(int i = 0; i < c; 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 < b; i++)
		  {
			  int i2 = i*3;
			  total += query_count.get(i);
			  if(total > 0)
			  {
				  add_count.set(operations.get(i2), add_count.get(operations.get(i2))+(operations.get(i2+2)*total));
				  add_count.set(operations.get(i2+1)+1, add_count.get(operations.get(i2+1)+1)+(-1*operations.get(i2+2)*total));
			  }
		  }
		  total = 0;
		  for(int i = 0; i < a; i++)
		  {
			  total += add_count.get(i);
			  System.out.print(arr.get(i)+total + " ");
		  }
	}
}
/*import java.util.Arrays;
import java.util.Scanner;

public class cf10 {
	public static void main(String[] args)
	{
		Scanner in = new Scanner(System.in);
	    int a = in.nextInt();
	    int b = in.nextInt();
	    int c = in.nextInt();
	    int[] intArr = new int[a];
	    int[] opArr = new int[b*3];
	    for(int x = 0; x < a; x++)
	    {
	    	intArr[x] = in.nextInt();
	    }
	    for(int x = 0; x < b; x++)
	    {
	    	int x2 = x*3;
	    	opArr[x2] = in.nextInt();
	    	opArr[x2+1] = in.nextInt();
	    	opArr[x2+2] = in.nextInt();
	    }
	    for(int x = 0; x < c; x++)
	    {
	    	int from = in.nextInt();
	    	int to = in.nextInt();
	    	for(; from <= to; from++)
	    	{
	    		int arrfrom = opArr[(from-1)*3];
	    		int arrto = opArr[((from-1)*3) + 1];
	    		int arrdelt = opArr[((from-1)*3) + 2];
	    		
	    		//int[] subArr = Arrays.copyOfRange(intArr, arrfrom, arrto);
	    		for(int x2 = arrfrom-1; x2 <= arrto-1; x2++)
	    		{
	    			//System.out.println("Adding " + arrdelt + " to " + intArr[x2]);
	    			intArr[x2] += arrdelt;
	    		}
	    		//System.out.print("OP done. Arr is: ");
	    		//for(int x3 = 0; x3 < intArr.length; x3++)
	    	    //{
	    	    	//System.out.print(intArr[x3] + " ");
	    	   // }
	    		//System.out.println();
	    	}
	    }
	    for(int x = 0; x < intArr.length; x++)
	    {
	    	System.out.print(intArr[x] + " ");
	    }
	}
}
*/