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
#!/usr/bin/env python
import sys

class Operation(object):
	def __init__(self, operation):
		self.left, self.right, self.increment = operation
		self.left -= 1
		self.right -= 1

class RangeAggregate(object):
	def __init__(self, range_sz):
		self.range_ = [ 0 ] * range_sz

	def range(self):
		current_aggregate = None
		for aggregate in self.range_:
			if current_aggregate is None:
				current_aggregate = aggregate
			else:
				current_aggregate += aggregate
			yield current_aggregate

	# left, right inclusive
	def merge(self, left, right, amount):
		self.range_[left] += amount
		if right + 1 < len(self.range_):
			self.range_[right + 1] -= amount

def merge(array_size, operations, queries):
	# merge queries
	query_aggregate = RangeAggregate(len(operations))
	for query in queries:
		query_aggregate.merge(query[0], query[1], 1)

	operation_aggregate = RangeAggregate(array_size)
	for operation, multiplier in zip(operations, query_aggregate.range()):
		operation_aggregate.merge(operation.left, operation.right, operation.increment * multiplier)

	result = operation_aggregate.range()
	return result

if __name__ == "__main__":
	array_sz, n_operations, n_queries = map(int, sys.stdin.readline().split())
	array = map(int, sys.stdin.readline().split())
	if len(array) != array_sz:
		raise Exception

	operations = [ None ] * n_operations
	for i in xrange(n_operations):
		operations[i] = Operation(map(int, sys.stdin.readline().split()))

	queries = [ None ] * n_queries
	for i in xrange(n_queries):
		queries[i] = [x - 1 for x in map(int, sys.stdin.readline().split())]

	# n_queries O(10^5), array_sz O(10^5), n_operations O(10^5)
	# n^3 too slow, need to merge queried operations
	addition = merge(array_sz, operations, queries)
	array = [sum(x) for x in zip(array, addition)]
	print " ".join(map(str, array))
