题目描述

学校有 $n$ 个班级，一开始每个班级的人数是 $a_1, a_2, \dots, a_n$。

现在需要进行 $q$ 次调整，第 $i$ 次调整形如「给编号在 $[l_i, r_i]$ 内的每个班级都增加 $c_i$ 人」（$c_i$ 可以为负数，表示减少）。

请你输出所有调整完成之后，每个班级的人数。

输入格式

第一行一个整数 $n$，表示班级数。

第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个班级的初始人数。

第三行一个整数 $q$，表示调整次数。

接下来 $q$ 行，每行三个整数 $l, r, c$，表示给编号在 $[l,r]$ 内的每个班级都增加 $c$ 人。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示调整完成后第 $i$ 个班级的人数。

数据范围

$1 \le n, q \le 2\times 10^5$，$0 \le a_i \le 1000$，$-1000 \le c \le 1000$，$1 \le l \le r \le n$。

样例

输入样例 1

5
10 15 20 18 12
2
2 4 3
1 3 2

输出样例 1

12 20 25 21 12

提示

样例中先给 $2\sim4$ 班各加 $3$ 人得到 $[10,18,23,21,12]$，再给 $1\sim3$ 班各加 $2$ 人得到 $[12,20,25,21,12]$。

做法：一维差分数组，区间加 $O(1)$，最后前缀和还原，总复杂度 $O(n+q)$。