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.*;
import java.util.*;
import java.math.*;

public class A implements Runnable {
	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer st;
	static Random rnd;

	class Query {
		int l, r;
		long d, howMuch;

		public Query(int l, int r, long d) {
			this.l = l;
			this.r = r;
			this.d = d;
		}
	}

	void solve() throws IOException {
		int n = nextInt(), m = nextInt(), k = nextInt();
		long[] arr = new long[n];
		for (int i = 0; i < n; i++)
			arr[i] = nextLong();
		Query[] queries = new Query[m];
		for (int i = 0; i < m; i++)
			queries[i] = new Query(nextInt() - 1, nextInt() - 1, nextLong());

		long[] secondMods = new long[m + 1];

		for (int i = 0; i < k; i++) {
			int l = nextInt() - 1, r = nextInt() - 1;
			secondMods[l]++;
			secondMods[r + 1]--;
		}

		long secondCur = 0;
		for (int i = 0; i < m; i++) {
			secondCur += secondMods[i];
			queries[i].howMuch = secondCur;
		}

		long[] firstMods = new long[n + 1];

		for (int i = 0; i < m; i++) {
			firstMods[queries[i].l] += queries[i].d * queries[i].howMuch;
			firstMods[queries[i].r + 1] -= queries[i].d * queries[i].howMuch;
		}

		long firstCur = 0;

		for (int i = 0; i < n; i++) {
			firstCur += firstMods[i];
			long res = arr[i] + firstCur;
			out.print(res);
			out.print((i + 1) == n ? "\n" : " ");
		}

	}

	public static void main(String[] args) {
		new A().run();
	}

	public void run() {
		try {
			final String className = this.getClass().getName().toLowerCase();

			try {
				in = new BufferedReader(new FileReader(className + ".in"));
				out = new PrintWriter(new FileWriter(className + ".out"));
				// in = new BufferedReader(new FileReader("input.txt"));
				// out = new PrintWriter(new FileWriter("output.txt"));
			} catch (FileNotFoundException e) {
				in = new BufferedReader(new InputStreamReader(System.in));
				out = new PrintWriter(System.out);
			}

			rnd = new Random();

			solve();

			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.exit(42);
		}
	}

	String nextToken() throws IOException {
		while (st == null || !st.hasMoreTokens()) {
			String line = in.readLine();

			if (line == null)
				return null;

			st = new StringTokenizer(line);
		}

		return st.nextToken();
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
}