G. Osu!Mania制霸计划

Osu! 是世界上最大的在线同性交友网站音乐播放器，而 Mania 是其中的一个硬核模式。

HonmonoKurimi 是 SEU 音游群的现任音游王，目前正在向 Osu!Mania 世界 rank1 发起冲击。受到前任音游王 thor0 的指点后，他决定完成一个前无古人的壮举：将所有现阶段的人类极限曲放进同一个 Beatmap（谱面），并同时达成世界首杀。

但是，将所有的 Beatmap 进行合并工程量巨大。由于 Object（物件）数量过多，导致游戏自带的 Editor（编辑器）在加载时就卡死。所以 HonmonoKurimi 找到了你，希望你能帮助他高效实现 Beatmap 的编辑。

我们可以将整个 Beatmap 简化为一个包含 $n$ 个元素的数列 $t$，其中的每个元素 $t_i$ 表示一个 Object 的出现时间。

在一些情况下（比如谱面对音或谱面混剪），我们需要对于一段时间内的 Object 进行整体的平移。在每次平移后，我们会对数列 $t$ 排序，使得 $t_i$ 单调递增。

经过事先估算，一共需要进行 $m$ 次整体平移。每次平移可以由三个变量 $\{l_i,r_i,x_i\}$ 进行描述，表示将出现时间处于 $[l_i,r_i]$ 间的所有 Object 全部增加 $x_i$ 个单位时间。但是若区间 $[l_i+x_i,r_i+x_i]$ 内存在未被平移的 Object，那么该平移无效。

请输出 $m$ 次平移后的 Beatmap。

第一行有一个正整数 $T(1\leq T\leq 20)$，表示数据的组数。

对于每组数据，第一行有 $2$ 个正整数 $n,m(1\leq n,m\leq 10^5,1\leq \sum n,\sum m\leq 5\times 10^5)$，分别表示 Object 数量和整体平移的次数。

接下来一行有 $n$ 个正整数 $t_i(1\leq t_i\leq 10^{12})$，表示每个 Object 的出现时间。数据保证有 $t_i<t_{i+1},1\leq i<n$。

接下来 $m$ 行，每行有 $3$ 个整数 $l_i,r_i(-10^{18}\leq l_i\leq r_i\leq 10^{18}),x_i(-10^{12}\leq x_i\leq 10^{12})$，分别表示每次整体平移的三个参数。

对于每组数据，输出一行 $n$ 个整数，表示 $m$ 次平移后的 Beatmap。

样例输入

1
5 3
1 2 3 4 5
1 3 -1
4 5 2
2 3 4

样例输出

0 1 2 6 7