题目描述

给定由 $n$ 个正整数组成的序列 $a_1, a_2, \cdots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，每个区间都有一个增加值$k_i$，代表这个区间的数全部增加$k_i$。最后需要输出增加完所有区间后的整个序列。

输入格式

第一行包含一个正整数 $n$，表示序列的长度。

第二行包含 $n$ 个正整数 $a_1,a_2, \cdots ,a_n$。

第三行包含一个正整数 $m$，表示区间的数量。

接下来 $m$ 行，每行包含三个正整数 $l_i,r_i,k_i$，满足 $1\le l_i\le r_i\le n$。

输出格式

共 一行 ,$n$个整数，其中第 $i$ 个整数，表示变化后的$a_i$。

输入输出样例 #1

输入 #1

5
9 8 9 8 5
2
1 2 3
4 5 10

输出 #1

12 11 9 18 15

数据范围

$1 \le n, m\le 10^5$，$1 \le a_i，k_i \le 10^4$。