题目描述

在一个模拟资源管理游戏中，玩家需要优化和提升一个村庄中居民的生产效率。

游戏中，玩家可以指派特定任务给一组居民，从而增加他们的生产能力。通过多次任务分配，玩家的目标是最大化整个村庄的生产效率。每个任务允许玩家选择一段连续的居民，并统一提升他们的生产能力。

现在，你的任务是帮助玩家计算完成所有任务后，每位居民的最终生产能力。

输入格式

第一行包含两个整数 $n$ 和 $p$，分别代表村庄居民数和任务数。

第二行包含 $n$ 个整数，$a_1 \sim a_n$，代表每位居民初始的生产能力值。

接下来 $p$ 行，每行包含三个整数 $x$，$y$，$z$，分别代表从第 $x$ 个到第 $y$ 个居民每人增加 $z$ 生产能力值。

输出格式

输出一行，表示所有任务完成后，每位居民的生产能力值。

输入样例1

3 2
1 1 1
1 2 1
2 3 1

输出样例1

2 3 2

输入样例2

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

输出样例2

18 22 15

数据范围

本题共有10个测试点。

对于测试点1-2，$1\leq n, p\leq 10$, $1\leq a_i, z\leq 10$。

对于测试点3-4，$1\leq n, p\leq 10^3$, $1\leq a_i, z\leq 10^3$。

对于测试点5-8，$1\leq n, p\leq 2\times 10^5$, $1\leq a_i, z\leq 10^3$。

对于测试点9-10，$1\leq n, p\leq 2\times 10^5$, $1\leq a_i, z\leq 10^9$。