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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;



public class Main{
		
		 public static void main(String[] args) throws IOException {
			 	PrintWriter out = new PrintWriter(System.out);
			    	MyScanner sc = new MyScanner();
			 	//Reader sc = new Reader();
			 	Main solver = new Main();
				solver.solve(out, sc);
				out.flush();
				out.close();
			
		 }
	
		
		 
		 
		 
		 
		void solve(PrintWriter out, MyScanner sc) throws IOException{	
			int n = sc.nextInt();
			int m = sc.nextInt();
			int k = sc.nextInt();
			long[] a = new long[n];
			int[] q = new int[m];
			operation[] o = new operation[m];
			
			for(int i = 0 ; i < n ; ++i) a[i] = sc.nextLong();
			for(int i = 0 ; i < m ; ++i) {
				int l = sc.nextInt() - 1;
				int r = sc.nextInt() - 1;
				Long d = sc.nextLong();
				o[i] = new operation(l, r, d);
			}
			for(int i = 0 ; i < k ; ++i) {
				int x = sc.nextInt() - 1;
				int y = sc.nextInt() - 1;
				q[x]++;
				if(y < m - 1) q[y + 1]--;
				
			}
			
			for(int i = 1 ; i < m ; ++i) q[i] += q[i - 1];
			long[] res = new long[n];
			for(int i = 0 ; i < m ; ++i) {
				res[o[i].l] += o[i].d * q[i];
				if(o[i].r < n - 1) res[o[i].r + 1] -= o[i].d * q[i];
			
			}
			for(int i = 1 ;i < n ; ++i) res[i] += res[i - 1];
			
			for(int i = 0 ; i < n ; ++i) out.print(a[i] + res[i] + " ");
			
			
			
	
		}
		
		
			
		static class operation{
			int l, r;
			long d;
			public operation(int l, int r, long d) {
				this.l = l;
				this.r = r;
				this.d = d;
			}
		}
		
		
		
		
		
		
		
		
		
		static class MyScanner {
		    BufferedReader br;
		    StringTokenizer st;

		    public MyScanner() {
		       br = new BufferedReader(new InputStreamReader(System.in));
		    }

		    String next() {
		        while (st == null || !st.hasMoreElements()) {
		            try {
		                st = new StringTokenizer(br.readLine());
		            } catch (IOException e) {
		                e.printStackTrace();
		            }
		        }
		        return st.nextToken();
		    } 

		    int nextInt() { return Integer.parseInt(next());}

		    long nextLong() {return Long.parseLong(next());}

		    double nextDouble() {return Double.parseDouble(next());}

		    String nextLine(){
		        String str = "";
			  try {
			     str = br.readLine();
			  } catch (IOException e) {
			     e.printStackTrace();
			  }
			  return str;
		    }
		    
		  
		    
		    
		    

		}
		
		
		static class Reader
	    {
	        final private int BUFFER_SIZE = 1 << 16;
	        private DataInputStream din;
	        private byte[] buffer;
	        private int bufferPointer, bytesRead;
	 
	        public Reader()
	        {
	            din = new DataInputStream(System.in);
	            buffer = new byte[BUFFER_SIZE];
	            bufferPointer = bytesRead = 0;
	        }
	 
	        public Reader(String file_name) throws IOException
	        {
	            din = new DataInputStream(new FileInputStream(file_name));
	            buffer = new byte[BUFFER_SIZE];
	            bufferPointer = bytesRead = 0;
	        }
	 
	        public String readLine() throws IOException
	        {
	            byte[] buf = new byte[64]; // line length
	            int cnt = 0, c;
	            while ((c = read()) != -1)
	            {
	                if (c == '\n')
	                    break;
	                buf[cnt++] = (byte) c;
	            }
	            return new String(buf, 0, cnt);
	        }
	 
	        public int nextInt() throws IOException
	        {
	            int ret = 0;
	            byte c = read();
	            while (c <= ' ')
	                c = read();
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	            do
	            {
	                ret = ret * 10 + c - '0';
	            }  while ((c = read()) >= '0' && c <= '9');
	 
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        public long nextLong() throws IOException
	        {
	            long ret = 0;
	            byte c = read();
	            while (c <= ' ')
	                c = read();
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	            do {
	                ret = ret * 10 + c - '0';
	            }
	            while ((c = read()) >= '0' && c <= '9');
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        public double nextDouble() throws IOException
	        {
	            double ret = 0, div = 1;
	            byte c = read();
	            while (c <= ' ')
	                c = read();
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	 
	            do {
	                ret = ret * 10 + c - '0';
	            }
	            while ((c = read()) >= '0' && c <= '9');
	 
	            if (c == '.')
	            {
	                while ((c = read()) >= '0' && c <= '9')
	                {
	                    ret += (c - '0') / (div *= 10);
	                }
	            }
	 
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        private void fillBuffer() throws IOException
	        {
	            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
	            if (bytesRead == -1)
	                buffer[0] = -1;
	        }
	 
	        private byte read() throws IOException
	        {
	            if (bufferPointer == bytesRead)
	                fillBuffer();
	            return buffer[bufferPointer++];
	        }
	 
	        public void close() throws IOException
	        {
	            if (din == null)
	                return;
	            din.close();
	        }
	    }
		
		
		 




			
		
		
}

