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
/*
 * Code Author: Akshay Miterani
 * DA-IICT
 */
import java.io.*;
import java.util.*;


public class SegTree {

	static int n;
	static int N;
	static final int size=100001;
	static Pair tree[]=new Pair[3*size];
	static long lazy[]=new long[3*size+1000];
	static long A[]=new long[3*size+1000];
	public static void main(String args[]){
		InputReader in = new InputReader(System.in);
		OutputStream outputStream = System.out;
		PrintWriter out = new PrintWriter(outputStream);
		//----------My Code Starts Here----------
		n=in.nextInt();
		int m=in.nextInt();
		int q=in.nextInt();
		int ind=(int)Math.pow(2,Math.ceil((Math.log(n)/Math.log(2))));;
		Pair updates[]=new Pair[m];
		for(int i=0;i<n;i++){
			A[i]=in.nextLong();
		}
		for(int i=0;i<3*size;i++){
			tree[i]=new Pair(0,0);
		}
		build(1, 0, n-1);
		/*
		for(int i=0;i<ind+n;i++){
			out.print(tree[i].x+" ");
		}
		*/
		for(int i=0;i<m;i++){
			updates[i]=new Pair(in.nextLong(),in.nextLong());
			updates[i].c=in.nextLong();
		}
		long partial[]=new long[m+1];
		for(int i=0;i<q;i++){
			int l=in.nextInt()-1;
			int r=in.nextInt();
			partial[l]++;
			partial[r]--;
		}
		long cur=0;
		for(int i=0;i<m;i++){
			cur+=partial[i];
			updates[i].c*=cur;
			//System.out.println(i+"->"+cur+" "+updates[i].c);
		}
		for(int i=0;i<m;i++){
			updateRange(1, 0, n-1, (int)updates[i].x-1, (int)updates[i].y-1, updates[i].c);
		}
		pushDown(1, 0, n-1);
		for(int i=0;i<n;i++){
			out.print(queryRange(1, 0, n-1, i, i).x+" ");
		}
		out.println();
		out.close();
		//---------------The End------------------
	}
	//========Segment Tree===========
	static void build(int node, int start, int end)
	{
	    if(start == end)
	    {
	        // Leaf node will have a single element
	        tree[node].x = A[start];
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        // Recurse on the left child
	        build(2*node, start, mid);
	        // Recurse on the right child
	        build(2*node+1, mid+1, end);
	        // Internal node will have the sum of both of its children
	        tree[node] = combine(tree[node*2],tree[node*2+1]);
	    }
	}
	static void update(int node, int start, int end, int idx, long val)
	{
	    if(start == end)
	    {
	        // Leaf node
	        A[idx] += val;
	        tree[node].x += val;
	    }
	    else
	    {
	        int mid = (start + end) / 2;
	        if(start <= idx && idx <= mid)
	        {
	            // If idx is in the left child, recurse on the left child
	            update(2*node, start, mid, idx, val);
	        }
	        else
	        {
	            // if idx is in the right child, recurse on the right child
	            update(2*node+1, mid+1, end, idx, val);
	        }
	        // Internal node will have the sum of both of its children
	        tree[node] = combine(tree[node*2],tree[node*2+1]);
	    }
	}
	static Pair query(int node, int start, int end, int l, int r)
	{
	    if(r < start || end < l)
	    {
	        // range represented by a node is completely outside the given range
	        return new Pair(0,0);
	    }
	    if(l <= start && end <= r)
	    {
	        // range represented by a node is completely inside the given range
	        return tree[node];
	    }
	    // range represented by a node is partially inside and partially outside the given range
	    int mid = (start + end) / 2;
	    Pair p1 = query(2*node, start, mid, l, r);
	    Pair p2 = query(2*node+1, mid+1, end, l, r);
	    return combine(p1,p2);
	}
	static Pair combine(Pair Left,Pair Right){
		Pair ret=new Pair(Left.x+Right.x,0);
		return ret;
	}
	//===========Lazy Updates========
	static void updateRange(int node, int start, int end, int l, int r, long val)
	{
		
	    if(lazy[node] != 0)
	    { 
	        // This node needs to be updated
	        tree[node].x += (end - start + 1) * lazy[node];    // Update it
	        if(start != end)
	        {
	            lazy[node*2] += lazy[node];                  // Mark child as lazy
	            lazy[node*2+1] += lazy[node];                // Mark child as lazy
	        }
	        lazy[node] = 0;                                  // Reset it
	    }
	    
	    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
	        return;
	    if(start >= l && end <= r)
	    {
	        // Segment is fully within range
	        tree[node].x += (end - start + 1) * val;
	        if(start != end)
	        {
	            // Not leaf node
	            lazy[node*2] += val;
	            lazy[node*2+1] += val;
	        }
	        return;
	    }
	    int mid = (start + end) / 2;
	    updateRange(node*2, start, mid, l, r, val);        // Updating left child
	    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
	    tree[node] =combine(tree[node*2],tree[node*2+1]);        // Updating root with max value 
	}
	static Pair queryRange(int node, int start, int end, int l, int r)
	{
	    if(start > end || start > r || end < l)
	        return new Pair(0,0);         // Out of range
	    if(lazy[node] != 0)
	    {
	        // This node needs to be updated
	        tree[node].x += (end - start + 1) * lazy[node];            // Update it
	        if(start != end)
	        {
	            lazy[node*2] += lazy[node];         // Mark child as lazy
	            lazy[node*2+1] += lazy[node];    // Mark child as lazy
	        }
	        lazy[node] = 0;                 // Reset it
	    }
	    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
	        return tree[node];
	    int mid = (start + end) / 2;
	    Pair p1 = queryRange(node*2, start, mid, l, r);         // Query left child
	    Pair p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
	    return combine(p1,p2);
	}
	static void pushDown(int node, int start, int end){
		if(start==end){
			tree[node].x+=lazy[node];
			lazy[node]=0;
			return;
		}
		if(lazy[node] != 0)
		    {
		        // This node needs to be updated
		        tree[node].x += (end - start + 1) * lazy[node];            // Update it
		        if(start != end)
		        {
		            lazy[node*2] += lazy[node];         // Mark child as lazy
		            lazy[node*2+1] += lazy[node];    // Mark child as lazy
		        }
		        lazy[node] = 0;                 // Reset it
		    }
		 int mid = (start + end) / 2;
		 pushDown(node*2, start, mid);         // Pushing Left Down
		 pushDown(node*2 + 1, mid + 1, end);
	}
	//===============================
	static class Pair implements Comparable<Pair>{
		long x;
		long y;
		long c;
		Pair(long xx,long yy){
			x=xx;
			y=yy;
		}
		@Override
		public int compareTo(Pair o) {
			return Long.compare((this.x),(o.x));
		}
	}
	
	static class InputReader {
	    public BufferedReader reader;
	    public StringTokenizer tokenizer;

	    public InputReader(InputStream inputstream) {
	      reader = new BufferedReader(new InputStreamReader(inputstream));
	      tokenizer = null;
	    }
	    
	    public String nextLine(){
	    	String fullLine=null;
	    	while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	              fullLine=reader.readLine();
	            } catch (IOException e) {
	              throw new RuntimeException(e);
	            }
	            return fullLine;
	          }
	          return fullLine;
	    }
		public String next() {
	      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	        try {
	          tokenizer = new StringTokenizer(reader.readLine());
	        } catch (IOException e) {
	          throw new RuntimeException(e);
	        }
	      }
	      return tokenizer.nextToken();
	    }
		public long nextLong() {
		      return Long.parseLong(next());
		    }
	    public int nextInt() {
	      return Integer.parseInt(next());
	    }
	  }
}