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

public class P295A
{
	public static void main(String[] args)
	{
		FastScanner scan = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int k = scan.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = scan.nextInt();
		Op[] op = new Op[m];
		for (int i = 0; i < m; i++)
			op[i] = new Op(scan.nextInt()-1, scan.nextInt()-1, scan.nextInt());
		SegTree tree1 = new SegTree(new int[m]);
		for (int i = 0; i < k; i++)
			tree1.addRange(scan.nextInt()-1, scan.nextInt()-1, 1);
		SegTree tree2 = new SegTree(arr);
		for (int i = 0; i < m; i++)
			tree2.addRange(op[i].left, op[i].right, op[i].add * tree1.get(i));
		for (int i = 0; i < n; i++)
			pw.print(tree2.get(i) + " ");
		pw.flush();
	}
	static class Op
	{
		int left, right;
		long add;
		Op(int l, int r, int a)
		{
			left = l;
			right = r;
			add = a;
		}
	}
	static class SegTree
	{
		class Range
		{
			int left, right;
			long val;
			Range(int l, int r)
			{
				left = l;
				right = r;
			}
		}
		Range[] ranges;
		int size, full, start, end;
		SegTree(int[] arr)
		{
			size = arr.length;
			full = Math.max(1, Integer.highestOneBit(size - 1) << 1);
			ranges = new Range[full * 2 - 1];
			start = full - 1;
			end = full * 2 - 2;
			setRanges();
			for (int i = start; i <= end; i++)
				ranges[i].val = i-start >= arr.length ? 0 : arr[i - start];
		}
		void setRanges()
		{
			for (int i = end; i >= 0; i--)
			{
				int left = i >= start ? i - start : ranges[i * 2 + 1].left;
				int right = i >= start ? i - start : ranges[i * 2 + 2].right;
				ranges[i] = new Range(left, right);
			}
		}
		long get(int index)
		{
			return getSum(start + index);
		}
		long getSum(int index)
		{
			if (index == 0)
				return ranges[0].val;
			return ranges[index].val + getSum((index - 1) / 2);
		}
		void addRange(int left, int right, long a)
		{
			addRange(left, right, a, 0);
		}
		private void addRange(int left, int right, long a, int root)
		{
			if (ranges[root].left == left && ranges[root].right == right)
				ranges[root].val += a;
			else if (ranges[root].right >= left && ranges[root].left <= right)
			{
				addRange(Math.max(left, ranges[2 * root + 1].left), Math.min(right, ranges[2 * root + 1].right), a, 2 * root + 1);
				addRange(Math.max(left, ranges[2 * root + 2].left), Math.min(right, ranges[2 * root + 2].right), a, 2 * root + 2);
			}
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
		}

		public String next()
		{
			if (st.hasMoreTokens())
				return st.nextToken();
			try
			{
				st = new StringTokenizer(br.readLine());
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return st.nextToken();
		}

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

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

		public String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}
