跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2475. Greg and Array

  • ID: 2481
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:基础
  • 上传者:
  • 数据结构
  • 模拟
  • 编程与模拟
  • 基础
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Greg and Array

题目描述

A. Greg and Array
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2110 题。保留原作者与原赛事署名。