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. 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. 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.