Description

    曾经有一个魔法师，他拥有一把能够让物品变得更强大的魔杖。一天，他来到了一个村庄，这个村庄里的人都很穷困，生活十分艰难。魔法师看到了这些人的状况，就决定用他的魔杖来帮助这些人。
    于是，他让村庄里的每一个人都拿出自己家里的一些东西，比如衣服、食物等等。然后，他开始对这些东西施展魔法，每次魔法都会让这些东西变得更加有用，更加有价值。
    具体来说，魔法师会先将这些东西全部放在一个大篮子里，然后依次进行施法。每次施法，他会选择一段区间[l, r]，然后将这个区间内的所有东西都加上一个数字m，使得这个区间内的所有数字都变成原来的数字+m。最后，魔法师将这些东西还给了村庄里的人，村庄里的人都非常高兴，因为他们现在拥有了更多更好的物品，生活变得更加美好了。
    现在，请你来帮助魔法师实现这个魔法，计算出每个位置的最终数值，让村庄里的人们过上更好的生活。

Input Format

第一行包含一个整数n。
第二行包含n个整数，表示初始的数组a。
第三行包含一个整数k，表示接下来有k个操作。
接下来m行，每行包含三个整数l，r，m，表示对a[l]到a[r]之间的元素加上m。

Output Format

共一行，包含n个整数，表示最终的数组a。

6
1 2 3 4 5 6
4
1 4 1
2 6 2
3 5 3
1 6 4

6 9 13 14 14 12

Hint

数据范围：

50% 1<=n<=5000，k<=100，1<=l<=r<=n；

100% 1<=n<=1000000，k<=10000，1<=l<=r<=n；

每个物品最终价值不会超过int范围

Source

前缀和 区间问题