题目描述

给你一个长度为 $n$ 的序列 $a$，有 $m$ 次操作，每次操作给出 $l,r,x$，要求执行下列代码：

for(int i=l;i<=r;i++)
    if(a[i]>x)
        a[i]-=x;

每次操作之后回答下列代码的 ans：

long long ans=0;
for(int i=1;i<=n;i++)
    ans+=a[i];

输入格式

第一行两个整数 $n,m$。

第 2 行 $n$ 个整数，第 $i$ 个整数为 $a_i$。

第 3 ～ $m+2$ 行，每行 3 个整数，分别表示这次操作的 $l,r,x$。

输出格式

每行一个整数，表示做完此次操作之后的全局和。

输入输出样例 #1

输入 #1

5 5
9 7 8 3 5
1 5 1
1 1 4
1 4 4
2 5 1
2 4 3

输出 #1

27
23
15
11
11

说明/提示

• Subtask 1（10 pts）： $1\le n,m\le 2\times 10^3$，$1\le a_i,x\le 10^9$。
• Subtask 2（20 pts）： $1\le n\le 2\times 10^3$，$1\le m\le 2\times 10^5$，$1\le a_i,x\le 10^9$。
• Subtask 3（20 pts）： $1\le n,m,a_i,x\le 2\times 10^5$。
• Subtask 4（50 pts）： $1\le n,m\le 5\times 10^5$，$1\le a_i,x\le 10^9$。