Greg has an array a = a_1, a_2, ..., a_{n} and m operations. Each operation looks as: l_{i}, r_{i}, d_{i}, (1 ≤ l_{i} ≤ r_{i} ≤ n). To apply operation i to the array means to increase all array elements with numbers l_{i}, l_{i} + 1, ..., r_{i} by value d_{i}.

Greg wrote down k queries on a piece of paper. Each query has the following form: x_{i}, y_{i}, (1 ≤ x_{i} ≤ y_{i} ≤ m). That means that one should apply operations with numbers x_{i}, x_{i} + 1, ..., y_{i} 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 ≤ 10^5). The second line contains n integers: a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^5) — the initial array.

Next m lines contain operations, the operation number i is written as three integers: l_{i}, r_{i}, d_{i}, (1 ≤ l_{i} ≤ r_{i} ≤ n), (0 ≤ d_{i} ≤ 10^5).

Next k lines contain the queries, the query number i is written as two integers: x_{i}, y_{i}, (1 ≤ x_{i} ≤ y_{i} ≤ m).

The numbers in the lines are separated by single spaces.


-----Output-----

On a single line print n integers a_1, a_2, ..., a_{n} — 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

Difficulty: competition

Starter code:

Solutions:
from sys import stdin, stdout

rd = lambda: list(map(int, stdin.readline().split()))

n, m, k = rd()
a = rd()
b = [rd() for _ in range(m)]
x = [0]*(m+1)
y = [0]*(n+1)

for _ in range(k):
  l, r = rd()
  x[l-1] += 1
  x[r  ] -= 1

s = 0
for i in range(m):
  l, r, d = b[i]
  s += x[i]
  y[l-1] += s*d
  y[r  ] -= s*d

s = 0
for i in range(n):
  s += y[i]
  a[i] += s
print(' '.join(map(str, a)))

n, m, k = map(int, input().split())
t = list(map(int, input().split()))
p = [tuple(map(int, input().split())) for i in range(m)]

r, s = [0] * (m + 1), [0] * (n + 1)
R, S = 0, 0

for i in range(k):
    x, y = map(int, input().split())
    r[x - 1] += 1
    r[y] -= 1

for i, (x, y, d) in enumerate(p):
    R += r[i]
    d = d * R
    s[x - 1] += d
    s[y] -= d

for i in range(n):
    S += s[i]
    t[i] = str(t[i] + S)

print(' '.join(map(str, t)))

read_input = lambda: list(map(int, input().split()))

n, m, k = read_input()
init_array = read_input()
operations = [read_input() for _ in range(m)]
additionals = [0]*(m+1)
sums = [0]*(n+1)

# Calculates the number of operations needed by using increments and decrements
for _ in range(k):
  x, y = read_input()
  additionals[x-1] += 1
  additionals[y  ] -= 1

# Calculates the operations times the number of times the operation is executed
sum_so_far = 0
for i in range(m):
  l, r, val_to_add = operations[i]
  sum_so_far += additionals[i]
  sums[l-1] += sum_so_far*val_to_add
  sums[r  ] -= sum_so_far*val_to_add

# Calculates the final number. Positives add while negatives remove
sum_so_far = 0
for i in range(n):
  sum_so_far += sums[i]
  init_array[i] += sum_so_far
print(' '.join(map(str, init_array)))

#import sys; sys.stdin = open("TF.txt")

R = lambda: list(map(int,input().split()))
def modif(lst):
    lst[0]-=1
    lst[1]-=1
    return lst
n,m,k = R()
a = R()
op = [modif(R()) for i in range(m)]
b = [0]*(n)
cnt = [0]*(m)
for i in range(k):
    l,r = R()
    l-=1;r-=1
    cnt[l] += 1
    try: cnt[r+1] -= 1
    except: pass
q = [0]*(m)
toadd  = 0
for i,v in enumerate(cnt):
    toadd += v
    q[i] += toadd
for i,v in enumerate(q):
    b[op[i][0]] += op[i][2] * v
    try: b[op[i][1]+1] -= op[i][2] * v
    except: pass
toadd = 0
for i,v in enumerate(b):
    toadd += v
    a[i] += toadd
print(*a)

def main():
    n, m, k = list(map(int, input().split()))
    aa = list(map(int, input().split()))
    lrd = list(tuple(map(int, input().split())) for _ in range(m))
    cnt = [0] * (m + 1)
    for _ in range(k):
        x, y = list(map(int, input().split()))
        cnt[x - 1] += 1
        cnt[y] -= 1
    delta, c = [0] * (n + 1), 0
    for (l, r, d), dc in zip(lrd, cnt):
        c += dc
        d *= c
        delta[l - 1] += d
        delta[r] -= d
    da = 0
    for i, a, d in zip(list(range(n)), aa, delta):
        da += d
        aa[i] = a + da
    print(" ".join(map(str, aa)))


def __starting_point():
    main()

__starting_point()

n, m, k = [int(n) for n in input().split()]
a = [int(n) for n in input().split()]
instructions = []
temp = []
for i in range(n+1):
	temp.append(0)
for i in range(m):
	instructions.append([int(n) for n in input().split()])
queries = []
for i in range(m+1):
	queries.append(0)
for i in range(k):
	x, y = [int(n) for n in input().split()]
	x-=1
	y-=1
	queries[x]+=1
	queries[y+1]-=1

num_queries = 0
for i in range(m):
	num_queries += queries[i]
	temp[instructions[i][0]-1] += num_queries*instructions[i][2]
	temp[instructions[i][1]] -= num_queries*instructions[i][2]
#print(temp[0]+a[0], end=" ")
x = temp[0]
print(x + a[0], end=" ")
for i in range(1, n):
	x += temp[i]
	print(x + a[i], end=" ")
print()

# -------
# imports
# -------

import sys


# -------
# solve
# -------

def solve(r, w):
    """
    :param r:
    :param w:
    :return:
    """
    data = r.readline().split()
    num_elems = int(data[0])
    num_ops = int(data[1])
    num_queries = int(data[2])

    elem_list = [int(x) for x in r.readline().split()]
    a = [0] * (num_ops + 1)
    b = [0] * (num_elems + 1)

    # get operations
    op_list = []
    for _ in range(num_ops):
        op_list.append(tuple([int(x) for x in r.readline().split()]))

    for _ in range(num_queries):
        query = [int(x) for x in r.readline().split()]
        a[query[0] - 1] += 1
        a[query[1]] -= 1

    c = 0
    for i, cur_op in enumerate(op_list):
        cur_op = op_list[i]
        c += a[i]
        b[cur_op[0] - 1] += c * cur_op[2]
        b[cur_op[1]] -= c * cur_op[2]

    c = 0
    for i, elem in enumerate(elem_list):
        c += b[i]
        print(elem + c, end=' ')


# -------
# main
# -------

def __starting_point():
    solve(sys.stdin, sys.stdout)

__starting_point()

from sys import *

rd = lambda: list(map(int, stdin.readline().split()))

n, m, k = rd()
a = rd()
b = [rd() for _ in range(m)]
x = [0]*(m+1)
y = [0]*(n+1)

for _ in range(k):
  l, r = rd()
  x[l-1] += 1
  x[r]   -= 1

s = 0
for i in range(m):
  l, r, d = b[i]
  s += x[i]
  y[l-1] += s*d
  y[r]   -= s*d

s = 0
for i in range(n):
  s += y[i]
  a[i] += s
print(*a)

#!/usr/bin/env python3

import sys

(n, m, k) = list(map(int, sys.stdin.readline().split(' ')))

a = list(map(int, sys.stdin.readline().split(' ')))
b = [0] * ((int)(1e5) + 1)
c = [0] * ((int)(1e5) + 1)
l = []
r = []
d = []

for i in range(m):
    (li, ri, di) = list(map(int, sys.stdin.readline().split(' ')))
    l.append(li)
    r.append(ri)
    d.append(di)

for i in range(k):
    (xi, yi) = list(map(int, sys.stdin.readline().split(' ')))
    c[xi - 1] += 1
    c[yi] -= 1

cur = 0
for i in range(0, m):
    cur += c[i]
    b[l[i]-1] += (cur*d[i])
    b[r[i]] -= (cur*d[i])

ret = []
cur = 0
for i in range(len(a)):
    num = b[i]
    cur += num
    ret.append(str(cur + a[i]))

sys.stdout.write(' '.join(ret) + '\n')


import sys

(n, m, k) = list(map(int, sys.stdin.readline().split(' ')))

a = list(map(int, sys.stdin.readline().split(' ')))
b = [0] * ((int)(1e5) + 1)
c = [0] * ((int)(1e5) + 1)
l = []
r = []
d = []

for i in range(m):
    (li, ri, di) = list(map(int, sys.stdin.readline().split(' ')))
    l.append(li)
    r.append(ri)
    d.append(di)

for i in range(k):
    (xi, yi) = list(map(int, sys.stdin.readline().split(' ')))
    c[xi - 1] += 1
    c[yi] -= 1

cur = 0
for i in range(0, m):
    cur += c[i]
    b[l[i]-1] += (cur*d[i])
    b[r[i]] -= (cur*d[i])

ret = []
cur = 0
for i in range(n):
    cur += b[i]
    ret.append(str(cur + a[i]))

sys.stdout.write(' '.join(ret) + '\n')


def GregAndArray():
    lenArray, numOperations, numQueries = map(int, input().split())
    initialArray = list(map(int, input().split()))
    
    instructions = [list(map(int, input().split())) for _ in range(numOperations)]
    
    modifiedArray = [0 for _ in range(lenArray + 1)]
    queries       = [0 for _ in range(numOperations + 1)]
    
    for _ in range(numQueries):
    	x, y = map(int, input().split())
    	
    	queries[x-1] += 1
    	queries[y]   -= 1
    
    temp = 0
    for i in range(numOperations):
    	temp += queries[i]
    	modifiedArray[instructions[i][0]-1] += temp*instructions[i][2]
    	modifiedArray[instructions[i][1]]   -= temp*instructions[i][2]
    
    temp = 0
    toReturn = ""
    for i in range(lenArray):
        temp += modifiedArray[i]
        toReturn += (str(temp + initialArray[i]) + " ")
    
    print(toReturn)

GregAndArray()

int_list = lambda s: [int(n) for n in s.split(" ")]
n,m,k = int_list(input())
arr = int_list(input())
operations = [int_list(input()) for _ in range(m)]

incrs = [0]*len(arr)      # Amount to increment running total when traversing arr
freq = [0]*m              # The number of times the corresponding operation is used
                          # stored in the same format as incrs

for _ in range(k):
  l,r = int_list(input())
  freq[l-1] += 1
  if r < len(freq): freq[r] -= 1
  
times = 0                   # number of times to apply current operation
for i, op in enumerate(operations):
  l,r,d = op
  times += freq[i]          # update running total
  incrs[l-1] += times*d     # encode operation in incrs
  if r < len(incrs): incrs[r] -= times*d
    
prev = 0
for i,n in enumerate(arr):
  arr[i] = prev + n + incrs[i]
  prev += incrs[i]
  
print(" ".join([str(n) for n in arr]))

def solve():
    n, m, k = list(map(int, input().strip().split()))
    array = list(map(int, input().strip().split()))
    ops = [tuple(map(int, input().strip().split())) for _ in range(m)]
    applied = [0 for _ in range(m + 1)]
    qs = [tuple(map(int, input().strip().split())) for _ in range(k)]
    for x, y in qs:
        applied[x - 1] += 1
        applied[y] -= 1
    cumadds = [0 for _ in range(n + 1)]
    repeats = 0
    for i, (l, r, d) in enumerate(ops):
        repeats += applied[i]
        cumadds[l - 1] += repeats * d
        cumadds[r] -= repeats * d
    cum = 0
    for i, cumadd in zip(list(range(n)), cumadds):
        cum += cumadd
        array[i] += cum
    print(*array)

solve()


int_list = lambda s: [int(n) for n in s.split(" ")]
n,m,k = int_list(input())
arr = int_list(input())
operations = [int_list(input()) for _ in range(m)]

incrs = [0]*len(arr)      # Amount to increment running total when traversing arr
freq = [0]*m              # The number of times the corresponding operation is used
                          # stored in the same format as incrs

for _ in range(k):
  l,r = int_list(input())
  freq[l-1] += 1
  if r < len(freq): freq[r] -= 1
  
times = 0                   # number of times to apply current operation
for i, op in enumerate(operations):
  l,r,d = op
  times += freq[i]          # update running total
  incrs[l-1] += times*d     # encode operation in incrs
  if r < len(incrs): incrs[r] -= times*d
    
prev = 0
for i,n in enumerate(arr):
  arr[i] = prev + n + incrs[i]
  prev += incrs[i]
  
print(" ".join([str(n) for n in arr]))

from itertools import accumulate

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
oper = [tuple(map(int, input().split())) for i in range(m)]
zapr = [tuple(map(int, input().split())) for i in range(k)]

count_ = [0 for i in range(m + 1)]

for el in zapr:
    x, y = el

    count_[x - 1] += 1
    count_[y] -= 1

counter_ = list(accumulate(count_))[:-1]

a.append(0)
a_count = [a[0]]

for i, el in enumerate(a[1:]):
    a_count.append(el - a[i])

for i, el in enumerate(oper):
    l, r, d = el
    d *= counter_[i]

    a_count[l - 1] += d
    a_count[r] -= d

a = list(accumulate(a_count))[:-1]

print(' '.join(map(str, a)))


def process_query(queries,m):
    n = len(queries)
    a = [0]*(m+1)
    for q in queries:
        a[q[0]-1] += 1; a[q[1]] -= 1
    for i in range(1,m):
        a[i] += a[i-1]
    return a[:-1]

def apply_query(times,updates,n):
    a = [0]*(n+1)
    # print(len(a),len(times),len(updates))
    for i in range(len(updates)):
        a[updates[i][0]-1] += times[i]*updates[i][2]
        a[updates[i][1]] -= times[i]*updates[i][2]
    for i in range(1,n):
        a[i] += a[i-1]
    return a[:-1]


def main():
    n, m, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    updates = [list(map(int, input().split())) for i in range(m)]
    queries = [list(map(int, input().split())) for i in range(k)]
    times_query = process_query(queries,m)
    # print("times_query",*times_query);
    updated_a = apply_query(times_query,updates,n)

    print(*[a[i] + updated_a[i] for i in range(n)])

def __starting_point():
    main()

__starting_point()

from sys import stdin, stdout
n,m,k = map(int,stdin.readline().split())
a = [0]
a = a + list(map(int,stdin.readline().split()))
op=[0]
mn = [0]*(m+2)
kp = [0]*(n+2)

for i in range(m):
    op.append(list(map(int,stdin.readline().split())))
for i in range(k):
    x,y = map(int,stdin.readline().split())
    mn[x]+=1
    mn[y+1]-=1
for i in range(1,m+1):
    mn[i]+=mn[i-1]
    op[i][2]*=mn[i]
    kp[op[i][0]]+=op[i][2]
    kp[op[i][1]+1]-=op[i][2]
for i in range(1,n+1):
    kp[i]+=kp[i-1]
for i in range(1,n+1):
    print(str(a[i]+kp[i]),end=" ")
    

def __starting_point():

    n, m, k = list(map(int, input().split()))

    nums = list(map(int, input().split()))

    operations = [tuple(map(int, input().split()))  for _ in range(m)]
    op_counter = [0] * (m+1)
    # queries
    for _ in range(k):
        x, y = list(map(int, input().split()))
        op_counter[x-1] += 1
        op_counter[y] -= 1

    acc = 0
    offset = [0]*(n+1)
    for i in range(m):
        l, r, d = operations[i]
        acc += op_counter[i]
        offset[l-1] += acc * d
        offset[r] -= acc * d

    acc = 0
    for i in range(n):
        acc += offset[i]
        nums[i] += acc
    print(' '.join(map(str, nums)))


__starting_point()