Osu! 是世界上最大的在线同性交友网站音乐播放器，而 Mania 是其中的一个硬核模式。
HonmonoKurimi 是 SEU 音游群的现任音游王，目前正在向 Osu!Mania 世界 rank1 发起冲击。受到前任音游王 thor0 的指点后，他决定完成一个前无古人的壮举：将所有现阶段的人类极限曲放进同一个 Beatmap（谱面），并同时达成世界首杀。
但是，将所有的 Beatmap 进行合并工程量巨大。由于 Object（物件）数量过多，导致游戏自带的 Editor（编辑器）在加载时就卡死。所以 HonmonoKurimi 找到了你，希望你能帮助他高效实现 Beatmap 的编辑。
我们可以将整个 Beatmap 简化为一个包含 n 个元素的数列 t，其中的每个元素 ti 表示一个 Object 的出现时间。
在一些情况下（比如谱面对音或谱面混剪），我们需要对于一段时间内的 Object 进行整体的平移。在每次平移后，我们会对数列 t 排序，使得 ti 单调递增。
经过事先估算，一共需要进行 m 次整体平移。每次平移可以由三个变量 {li,ri,xi} 进行描述，表示将出现时间处于 [li,ri] 间的所有 Object 全部增加 xi 个单位时间。但是若区间 [li+xi,ri+xi] 内存在未被平移的 Object，那么该平移无效。
请输出 m 次平移后的 Beatmap。
第一行有一个正整数 T(1≤T≤20)，表示数据的组数。
对于每组数据，第一行有 2 个正整数 n,m(1≤n,m≤105,1≤∑n,∑m≤5×105)，分别表示 Object 数量和整体平移的次数。
接下来一行有 n 个正整数 ti(1≤ti≤1012)，表示每个 Object 的出现时间。数据保证有 ti<ti+1,1≤i<n。
接下来 m 行，每行有 3 个整数 li,ri(−1018≤li≤ri≤1018),xi(−1012≤xi≤1012)，分别表示每次整体平移的三个参数。
对于每组数据，输出一行 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