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
/*
If you want to aim high, aim high
Don't let that studying and grades consume you
Just live life young
******************************
If I'm the sun, you're the moon
Because when I go up, you go down
*******************************
I'm working for the day I will surpass you
https://www.a2oj.com/Ladder16.html
*/
import java.util.*;
import java.io.*;
import java.math.*;

   public class x295A
   {
      public static void main(String omkar[]) throws Exception
      {
         BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));  
         StringTokenizer st = new StringTokenizer(infile.readLine());
         int N = Integer.parseInt(st.nextToken());
         int M = Integer.parseInt(st.nextToken());
         int Q = Integer.parseInt(st.nextToken());
         StringBuilder sb = new StringBuilder();
         int[] arr = new int[N];
         st = new StringTokenizer(infile.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         Oper[] arr2 = new Oper[M];
         for(int i=0; i < M; i++)
         {
            st = new StringTokenizer(infile.readLine());
            int K = Integer.parseInt(st.nextToken())-1;
            int s = Integer.parseInt(st.nextToken())-1;
            int d = Integer.parseInt(st.nextToken());
            arr2[i] = new Oper(K,s,d);
         }
         int[] changes = new int[M];
         while(Q-->0)
         {
            st = new StringTokenizer(infile.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            changes[a-1]++;
            if(b < M)
               changes[b]--;
         }
         //print
         RangeTree res = new RangeTree(N+2);
         for(int i=1; i <= N; i++)
            res.update(i-1, i-1, arr[i-1]);
         long curr = changes[0];
         for(int i=0; i < M; i++)
         {
            long addend = (long)curr*(long)arr2[i].d;
            int left = arr2[i].l;
            int right = arr2[i].r;
            res.update(left, right, addend);
            if(i+1 < M)
               curr += changes[i+1];
         }
         for(int i=0; i < N; i++)
            sb.append(res.sumQuery(i, i)).append(" ");
         System.out.println(sb);
      }
   }
   class Oper
   {
      public int l;
      public int r;
      public int d;
      
      public Oper(int a, int b, int c)
      {
         l = a;
         r = b;
         d = c;
      }
   }
   class RangeTree 
   {
		private long[] lazy;
		private long[] sum;
		private int size;
		public RangeTree(int size) 
      {
			this.size = size;
			sum = new long[4*size];
			lazy = new long[4*size];
		}
		public void update(int l, int r, long inc) 
      {
			update(1, 0, size-1, l, r, inc);
		}
		private void pushDown(int index, int l, int r) 
      {
			sum[index] += lazy[index] * (r-l+1);
			if(l != r) 
         {
				lazy[2*index] += lazy[index];
				lazy[2*index+1] += lazy[index];
			}
			lazy[index] = 0;
		}
		private void pullUp(int index, int l, int r) 
      {
			int m = (l+r)/2;
			sum[index] = evaluateSum(2*index, l, m) + evaluateSum(2*index+1, m+1, r);
		}
		private long evaluateSum(int index, int l, int r) 
      {
			return sum[index] + (r-l+1)*lazy[index];
		}
		private void update(int index, int l, int r, int left, int right, long inc) 
      {
			if(r < left || l > right) return;
			if(l >= left && r <= right) {
				lazy[index] += inc;
				return;
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			update(2*index, l, m, left, right, inc);
			update(2*index+1, m+1, r, left, right, inc);
			pullUp(index, l, r);
		}
		public long sumQuery(int l, int r) 
      {
			return sumQuery(1, 0, size-1, l, r);
		}
		private long sumQuery(int index, int l, int r, int left, int right) 
      {
			if(r < left || l > right) return 0;
			if(l >= left && r <= right) {
				return evaluateSum(index, l, r);
			}
			pushDown(index, l, r);
			int m = (l+r)/2;
			long ret = 0;
			ret += sumQuery(2*index, l, m, left, right);
			ret += sumQuery(2*index+1, m+1, r, left, right);
			pullUp(index, l, r);
			return ret;
		}
	}