← 返回题目列表

Codeforces · 295/A

A. 格雷格和阵列

中文机器翻译题面 查看原题

Greg 有一个数组 a = a1, a2, ..., an 和 m 运算。每个操作看起来为:li, ri, di, (1 ≤ li ≤ ri ≤ n)。将操作 i 应用于数组意味着将所有编号为 li, li + 1, ..., ri 的数组元素增加值 di。

Greg 在一张纸上写下了 k 个查询。每个查询具有以下形式:xi, yi, (1 ≤ xi ≤ yi ≤ m)。这意味着应该对数组应用数字 xi, xi + 1, ..., yi 的运算。

现在 Greg 想知道,执行完所有查询后数组 a 会是什么。帮助格雷格。

输入

第一行包含整数 n、m、k (1 ≤ n、m、k ≤ 105)。第二行包含 n 个整数:a1, a2, ..., an (0 ≤ ai ≤ 105) — 初始数组。

接下来 m 行包含操作,操作号 i 写为三个整数:li、ri、di、(1 ≤ li ≤ ri ≤ n)、(0 ≤ di ≤ 105)。

接下来的 k 行包含查询,查询号 i 写为两个整数:xi,yi,(1 ≤ xi ≤ yi ≤ m)。

行中的数字由单个空格分隔。

输出

在单行上打印 n 个整数 a1, a2, ..., an — 执行所有查询后的数组。用空格分隔打印的数字。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 %I64d 说明符的 cin、cout 流。

示例

输入 #1

3 3 3
1 2 3
1 2 1
1 3 2
2 3 4
1 2
1 3
2 3

输出 #1

9 18 17

输入 #2

1 1 1
1
1 1 1
1 1

输出 #2

2

输入 #3

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

输出 #3

5 18 31 20