Greg has an array *a* = *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> and *m* operations. Each operation looks as: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*). To apply operation *i* to the array means to increase all array elements with numbers *l*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub> + 1, ..., *r*<sub class="lower-index">*i*</sub> by value *d*<sub class="lower-index">*i*</sub>.

Greg wrote down *k* queries on a piece of paper. Each query has the following form: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*). That means that one should apply operations with numbers *x*<sub class="lower-index">*i*</sub>, *x*<sub class="lower-index">*i*</sub> + 1, ..., *y*<sub class="lower-index">*i*</sub> to the array.

Now Greg is wondering, what the array *a* will be after all the queries are executed. Help Greg.
The first line contains integers *n*, *m*, *k* (1 ≤ *n*, *m*, *k* ≤ 10<sup class="upper-index">5</sup>). The second line contains *n* integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>) — the initial array.

Next *m* lines contain operations, the operation number *i* is written as three integers: *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>, *d*<sub class="lower-index">*i*</sub>, (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*), (0 ≤ *d*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">5</sup>).

Next *k* lines contain the queries, the query number *i* is written as two integers: *x*<sub class="lower-index">*i*</sub>, *y*<sub class="lower-index">*i*</sub>, (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *y*<sub class="lower-index">*i*</sub> ≤ *m*).

The numbers in the lines are separated by single spaces.
import sys
import string
import math
from collections import defaultdict
from functools import lru_cache
from collections import Counter
from fractions import Fraction

def mi(s):
    return map(int, s.strip().split())

def lmi(s):
    return list(mi(s))

def tmi(s):
    return tuple(mi(s))

def mf(f, s):
    return map(f, s)

def lmf(f, s):
    return list(mf(f, s))

def js(lst):
    return " ".join(str(d) for d in lst)

def jsns(lst):
    return "".join(str(d) for d in lst)

def line():
    return sys.stdin.readline().strip()

def linesp():
    return line().split()

def iline():
    return int(line())

def mat(n):
    matr = []
    for _ in range(n):
        matr.append(linesp())
    return matr

def matns(n):
    mat = []
    for _ in range(n):
        mat.append([c for c in line()])
    return mat

def mati(n):
    mat = []
    for _ in range(n):
       mat.append(lmi(line())) 
    return mat

def pmat(mat):
    for row in mat:
        print(js(row))

def main():
    n, m, k = mi(line())
    arr = lmi(line())
    ops = []
    for _ in range(m):
        x, y, d = lmi(line())
        ops.append((x - 1, y - 1, d))
    queries = []
    for _ in range(k):
        x, y = lmi(line())
        queries.append((x - 1, y - 1))
    
    sweep = []
    for x, y in queries:
        sweep.append((x, "add"))
        
        # Basically increment all windows by 1, so
        # that we don't have to care about annoying edge
        # cases for window size == 1.
        sweep.append((y + 1, "remove"))

    sweep.sort(key=lambda x: x[0])
    size = 0
    i = 0
    disjoint_queries = []
    prev_x = None
    while i < len(sweep):
        curr_x = sweep[i][0]
        j = i
        to_remove = 0
        prev_size = size
        while j < len(sweep):
            if sweep[j][0] != curr_x:
                break
            x, op = sweep[j]
            if op == "add":
                size += 1
            elif op == "remove":
                to_remove += 1
            j += 1
        i = j
        
        if prev_size > 0:
            # Don't care about size zero here.
            disjoint_queries.append((prev_x, curr_x, prev_size))
        prev_x = curr_x
        size -= to_remove

    new_ops = []
    for i in range(len(disjoint_queries)):
        l, r, size = disjoint_queries[i]
        if r - 1 >= l and size >= 1:
            for kk in range(l, r):
                x, y, d = ops[kk]
                new_ops.append((x, y, d * size))

    # Merge these intervals.
    sweep = []
    for x, y, d in new_ops:
        sweep.append((x, "add", d))
        
        # Basically increment all windows by 1, so
        # that we don't have to care about annoying edge
        # cases for window size == 1.
        sweep.append((y + 1, "remove", d))

    size = 0
    i = 0
    disjoint_ops = []
    prev_x = None
    while i < len(sweep):
        curr_x = sweep[i][0]
        j = i
        to_remove = 0
        prev_size = size
        while j < len(sweep):
            if sweep[j][0] != curr_x:
                break
            x, op, d = sweep[j]
            if op == "add":
                size += d
            elif op == "remove":
                to_remove += d
            j += 1
        i = j
        
        if prev_size > 0:
            # Don't care about size zero here.
            disjoint_ops.append((prev_x, curr_x, prev_size))
        prev_x = curr_x
        size -= to_remove

    for l, r, d in disjoint_ops:
        if r - 1 >= l:
            for kk in range(l, r):
                arr[kk] += d

    print(js(arr))
main()

class BSTNode(object):
    def __init__(self, val):
        self.val = val
        self.disconnect()

    def disconnect(self):
        self.left = None
        self.right = None
        self.parent = None


class BST(object):
    Node = BSTNode
    def __init__(self):
        self.root = None

    @staticmethod
    def minimum(node):
        """Finds and returns the minimum node
        in the sub-tree rooted at 'node'.
        """

        if node.left is None:
            return node
        else:
            return BST.minimum(node.left)

    def find(self, val):
        """Searches for val in the BST.

        If found, returns the node, else
        return None.
        """

        def rec_find(node):
            if not node:
                return None
            elif node.val == val:
                return node
            
            if node.val <= val:
                return rec_find(node.right)
            else:
                return rec_find(node.left)

        return rec_find(self.root)

    def __contains__(self, val):
        return bool(self.find(val))

    def insert(self, val):
        """Inserts the val into the BST.

        Returns the newly inserted node.
        """

        def rec_insert(node):
            if node.val <= val:
                if not node.right:
                    node.right = new_node
                    new_node.parent = node
                else:
                    rec_insert(node.right)
            else:
                if not node.left:
                    node.left = new_node
                    new_node.parent = node
                else:
                    rec_insert(node.left)

        new_node = self.Node(val)
        if not self.root:
            self.root = new_node
        else:
            rec_insert(self.root)

        return new_node

    def delete(self, val):
        """Deletes the node corresposnding to val
        from the BST. 

        Returns a (deleted node, parent node) tuple."""

        def fix_attrs(node, new_node):
            if node.parent:
                if node is node.parent.left:
                    node.parent.left = new_node
                else:
                    node.parent.right = new_node
            else:
                self.root = new_node

            if new_node:
                new_node.parent = node.parent

        def delete_node(node):
            if node.left and node.right:
                right_minimum = self.minimum(node.right)
                right_minimum.val, node.val = node.val, right_minimum.val
                return delete_node(right_minimum)
            elif node.left:
                new_node = node.left
            else:
                new_node = node.right
            fix_attrs(node, new_node)
            parent = node.parent
            node.disconnect()
            return node, parent

        to_delete = self.find(val)
        if not to_delete:
            return (None, None)
        else:
            return delete_node(to_delete)

    def __str__(self):
        """
        Prints the BST in a visually pleasing format.

        Code for this function acquired from
        MIT OCW 6.006 lecture code.
        """
        if self.root is None: return '<empty tree>'
        def recurse(node):
            if node is None: return [], 0, 0
            label = str(node.val)
            left_lines, left_pos, left_width = recurse(node.left)
            right_lines, right_pos, right_width = recurse(node.right)
            middle = max(right_pos + left_width - left_pos + 1, len(label), 2)
            pos = left_pos + middle // 2
            width = left_pos + middle + right_width - right_pos
            while len(left_lines) < len(right_lines):
                left_lines.append(' ' * left_width)
            while len(right_lines) < len(left_lines):
                right_lines.append(' ' * right_width)
            if (middle - len(label)) % 2 == 1 and node.parent is not None and \
               node is node.parent.left and len(label) < middle:
                label += '.'
            label = label.center(middle, '.')
            if label[0] == '.': label = ' ' + label[1:]
            if label[-1] == '.': label = label[:-1] + ' '
            lines = [' ' * left_pos + label + ' ' * (right_width - right_pos),
                     ' ' * left_pos + '/' + ' ' * (middle-2) +
                     '\\' + ' ' * (right_width - right_pos)] + \
              [left_line + ' ' * (width - left_width - right_width) +
               right_line
               for left_line, right_line in zip(left_lines, right_lines)]
            return lines, pos, width
        return '\n'.join(recurse(self.root) [0])


def height(node):
    if not node:
        return -1
    else:
        return node.height


def update_height(node):
    node.height = 1 + max(height(node.left), height(node.right))


def balanced(node):
        """Returns True if the AVL property is maintained
        for the given node.
        """
        return abs(height(node.left) - height(node.right)) <= 1


class AVLNode(BSTNode):
    """An AVLNode is a BSTNode with a height attribute."""
    def __init__(self, val):
        super(AVLNode, self).__init__(val)
        self.height = 0


class AVL(BST):
    """A BST which maintains O(log(n)) height using by maintaining
    the AVL property.
    """

    Node = AVLNode

    def rotate_left(self, node):
        right_node = node.right

        # Left rotate is not possible
        # when node.right is None.
        if not right_node:
            raise ValueError("Left rotate not possible.")

        if node.parent:
            if node is node.parent.left:
                node.parent.left = right_node
            else:
                node.parent.right = right_node
        else:
            self.root = right_node

        node.parent, right_node.parent = right_node, node.parent

        right_left_node = right_node.left
        if right_left_node:
            right_left_node.parent = node

        right_node.left = node
        node.right = right_left_node

        update_height(node)
        update_height(right_node)

        return node, right_node

    def rotate_right(self, node):
        left_node = node.left

        # Right rotate is not possible
        # when node.left is None.
        if not left_node:
            raise ValueError("Right rotate not possible.")

        if node.parent:
            if node is node.parent.left:
                node.parent.left = left_node
            else:
                node.parent.right = left_node
        else:
            self.root = left_node

        node.parent, left_node.parent = left_node, node.parent

        left_right_node = left_node.right
        if left_right_node:
            left_right_node.parent = node

        left_node.right = node
        node.left = left_right_node

        update_height(node)
        update_height(left_node)

        return node, left_node

    def fix_one_imbalance(self, node):
        """Fixes an AVL imbalance for the given node.

        We assume that this function is only called when an imbalance exists."""

        left_heavy = height(node.left) > height(node.right)

        if left_heavy:
            left_left_heavy = height(node.left.left) >= height(node.left.right)
            if left_left_heavy:
                self.rotate_right(node)
            else:
                self.rotate_left(node.left)
                self.rotate_right(node)
        else:
            right_right_heavy = height(node.right.right) >= height(node.right.left)
            if right_right_heavy:
                self.rotate_left(node)
            else:
                self.rotate_right(node.right)
                self.rotate_left(node)

    def fix_tree_imbalance(self, node):
        if node is None:
            return

        parent = node.parent
        update_height(node)

        if not balanced(node):
            self.fix_one_imbalance(node)

        self.fix_tree_imbalance(parent)

    def insert(self, val):
        """Overrides the insert method of BST.

        Updates heights and rotates.
        """
        new_node = super(AVL, self).insert(val)
        self.fix_tree_imbalance(new_node)

        return new_node

    def delete(self, val):
        """Overrides the delete method of BST.

        Updates heights and rotates.
        """
        deleted, parent = super(AVL, self).delete(val)

        if deleted and parent:
            self.fix_tree_imbalance(parent)

        return deleted, parent


def size(node):
    if not node:
        return 0
    else:
        return node.size


def update_size(node):
    node.size = 1 + size(node.left) + size(node.right)


class OSNode(AVLNode):
    def __init__(self, val):
        super(OSNode, self).__init__(val)
        self.size = 0


class OSTree(AVL):
    """An AVL tree which maintains the subtree size in each node."""
    
    Node = OSNode

    def rotate_left(self, node):
        old_top, new_top = super(OSTree, self).rotate_left(node)
        update_size(old_top)
        update_size(new_top)

    def rotate_right(self, node):
        old_top, new_top = super(OSTree, self).rotate_right(node)
        update_size(old_top)
        update_size(new_top)

    def fix_subtree_size(self, node):
        if node is None:
            return

        update_size(node)
        self.fix_subtree_size(node.parent)

    def insert(self, val):
        new_node = super(OSTree, self).insert(val)
        self.fix_subtree_size(new_node)

    def delete(self, val):
        deleted, parent = super(OSTree, self).delete(val)

        if deleted and parent:
            self.fix_subtree_size(parent)

    def get_ranked_node(self, rank):
        """Returns the node with the given rank.

        If rank is greater than the number of nodes in the tree,
        returns None.
        """
        if rank > self.root.size:
            return None

        def rec_rank(node, r):
            curr_rank = 1 + size(node.left)
            
            if curr_rank == r:
                return node
            elif curr_rank < r:
                return rec_rank(node.right, r - curr_rank)
            else:
                return rec_rank(node.left, r)

        return rec_rank(self.root, rank)

    def LCA(self, l, h):
        def rec_LCA(node):
            if node == None:
                return

            if l <= node.val <= h:
                return node
            elif l <= node.val:
                return rec_LCA(node.left)
            else:
                return rec_LCA(node.right)

        return rec_LCA(self.root)

    def gen_node_lst(self, node, l, h, result):
        if not node:
            return

        if l <= node.val <= h:
            result.append(node.val)

        if node.val >= l:
            self.gen_node_lst(node.left, l, h, result)

        if node.val <= h:
            self.gen_node_lst(node.right, l, h, result)

    def get_list_in_range(self, l, h):
        """Returns a list of all the values k such that l <= k <= h."""
        
        # The node which is the lca of the two nodes l, h.
        # l, h could be phantom nodes.
        lca = self.LCA(l, h)
        result = []
        self.gen_node_lst(lca, l, h, result)
        return result

    def rank(self, val):
        """Returns the number of nodes with node.val <= val."""
        def rec_rank(node, curr_rank):
            if node is None:
                return curr_rank

            if val == node.val:
                return curr_rank + 1 + size(node.left)
            elif val < node.val:
                return rec_rank(node.left, curr_rank)
            else:
                return rec_rank(node.right, curr_rank + 1 + size(node.left))

        return rec_rank(self.root, 0)

    def count_in_range(self, l, h):
        """Returns the number of nodes k such that l <= k <= h."""
        if l in self:
            return self.rank(h) - self.rank(l) + 1
        else:
            return self.rank(h) - self.rank(l)
