题目背景

译自 Izborne Pripreme 2017 (Croatian IOI/CEOI Team Selection) 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$。

输出格式

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

10 3
3 5 5 4 3 6 10 0 4 7
2 10 9
6 6 2
2 8 4

6
3
4

8 5
2 3 0 9 2 6 0 6
5 6 8
3 4 7
3 8 8
8 8 7
6 7 9

6
7
6
6
7

提示

对于 $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$。

再次提醒，每个窃贼的行窃是独立的，不互相影响。