题目描述

徐老师和他的 $n$ 个好朋友每人手里都拿着一些糖果，第 $i$ 个小伙伴的糖果数记为 $a_i$。

徐老师有一个可爱的魔法小助手，接下来它要按照指令对大家的糖果进行 $m$ 次调整。

• 第 $i$ 次调整时，徐老师会给出三个指令：$l_i、r_i、k_i$（$l_i$ 到 $r_i$ 表示从第 $l_i$ 个到第 $r_i$ 个小伙伴，包括两端）。
• 小助手会根据指令，执行 $k_i$ 次操作，每次操作会在第 $l_i$ 到 $r_i$ 个小伙伴中，找到糖果最少的那个（如果有多个小伙伴糖果数相同且最少，就选位置更靠前的那个），并给这个小伙伴再添 $1$ 颗糖果。

经过这 $m$ 次调整后，每个小伙伴手里最终有多少颗糖果呢？请你算一算并告诉大家吧。

输入格式

第一行一个正整数代表 $n$。

接下来一行 $n$ 个空格分隔的整数，代表 $a_1, a_2, ..., a_n$。

接下来一行一个正整数代表 $m$。

接下来 $m$ 行，第 $i$ 行包含三个空格分隔的正整数分别代表 $l_i, \ r_i,\ k_i$。

输出格式

输出一行 $n$ 个空格分隔的整数，代表答案。

输入输出样例1

6
4 2 7 2 5 1
3
1 6 3
4 6 10
2 4 10

4 9 9 9 7 6

数据范围与提示

样例一解释

4 2 7 2 5 1
|
|  1 6 3
V
4 3 7 3 5 2
|
|  4 6 10
V
4 3 7 7 7 6
|
|  2 4 10
V
4 9 9 9 7 6

说明

对于所有样例数据有：$1\le n \le 1000$，$1\le m \le 1000$，$1\le l_i \le r_i \le n$，$1\le a_i, a_i \le 10^9$。