#include <iostream>
#include <vector>
#include <map>
using namespace std;
/**
* NOI 2025 Singapore Preliminary - Task 3: Snacks
* 思路：使用 map 维护每种美味度出现的次数。
* 每次查询删除指定范围内的 key，并合并到一个新 key 中。
* 摊还分析下，复杂度为 O((N+Q) log N)。
*/
int main() {
// 优化输入输出
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
if (!(cin >> n >> q)) return 0;
map<long long, long long> counts;
long long total_sum = 0;
// 读取初始零食
for (int i = 0; i < n; ++i) {
long long a;
cin >> a;
counts[a]++;
total_sum += a;
}
// 1. 输出初始总和
cout << total_sum << "\n";
// 2. 处理 Q 次查询
for (int j = 0; j < q; ++j) {
long long l, r, x;
cin >> l >> r >> x;
// 查找范围 [l, r] 内的所有美味度
auto it = counts.lower_bound(l);
long long removed_num_of_snacks = 0;
while (it != counts.end() && it->first <= r) {
long long val = it->first;
long long num = it->second;
total_sum -= (val * num); // 减去旧贡献
removed_num_of_snacks += num; // 记录移除的零食总数
it = counts.erase(it); // 删除当前 key，erase 返回下一个迭代器
}
// 插入新的零食（如果有零食被替换）
if (removed_num_of_snacks > 0) {
counts[x] += removed_num_of_snacks;
total_sum += (x * removed_num_of_snacks);
}
// 输出当前总和
cout << total_sum << "\n";
}
return 0;
}
