P11286 [COTS 2017] 盗道 Krimošten

译自 [Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2017/) D1T2。$\texttt{4s,0.5G}$。 库纳（Kuna）是克罗地亚的货币单位。

海岸线上有一排房子，从西到东标号 $1\sim n$。第 $i$ 座房子内有 $a_i$ 库纳。 有 $m$ 个窃贼要行窃。第 $i$ 个窃贼初始囊中有 $c_i$ 库纳，他将依次对编号为 $l_i,l_i+1,\cdots, r_i$ 的房子行窃。 盗亦有道，窃贼们践行盗之道。当窃贼对编号为 $j$ 的房子行窃时，令他囊中有 $k$ 库纳： - 若 $k\lt a_j$，则窃贼将 $1$ 库纳收入囊中，即 $k\gets k+1$； - 若 $k=a_j$，无事发生； - 若 $k\gt a_j$，则窃贼拿出 $1$ 库纳赠给房主，即 $k\gets k-1$。 对于每个窃贼，求出他最后囊中会有多少库纳。 需要注意的是，**每个窃贼的行窃是独立的，不互相影响**。换句话说，可以认为一个窃贼行窃结束后，（在下一个窃贼行窃前）房子会恢复到初始状态。

第一行，两个正整数 $n,m$; 第二行，$n$ 个非负整数 $a_1,a_2,\cdots,a_n$; 接下来 $m$ 行，每行三个整数 $l_i,r_i,c_i$。

对于每个询问，输出一行一个整数表示答案。

对于 $100\%$ 的数据，保证： - $1\le n\le 5\times 10^5$； - $0\le a_i,c_i\le 10^6$； - $1\le l_i\le r_i\le n $。 | 子任务编号 | $n\le $ | $m\le $ |得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 10^3 $ | $10^3$ | $ 7 $ | | $ 2 $ | $ 5\times 10^4 $ | $10^5$ | $ 48 $ | | $ 3 $ | $ 5\times 10^5 $ | $5\times 10^5$ | $ 45 $ | 再次提醒，**每个窃贼的行窃是独立的，不互相影响**。