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