沙尘暴

题目描述

阿拉基斯的新建筑师正在设计一个由 $n$ 栋建筑排成一排的新街区。第 $i$ 栋建筑恰好有 $h_i$ 层。

现在建筑师想知道市民们是否能充分欣赏他的设计。问题在于城市中经常发生沙尘暴，而城墙只能保护低层建筑免受沙尘暴侵袭，因此一些建筑的高层可能从地面上看不到。

形式化地，你会收到形如 $(l, r, f)$ 的请求：“第 $l$ 到第 $r$ 栋建筑周围的沙尘暴等级变为 $f$”。这意味着，对于第 $l$ 到第 $r$ 栋建筑，只有前 $f$ 层是可见的，而所有更高的楼层都被沙子隐藏而不可见。每次请求后，你需要告诉建筑师当前所有建筑总共可见的层数是多少。

再次强调，沙尘暴是向上连续的，即如果第 $y$ 栋建筑的第 $x$ 层被沙子隐藏，那么第 $x+1, x+2, \ldots, h_y$ 层也被隐藏，只有第 $1$ 到第 $(x-1)$ 层可见。

初始时，在第一个请求到来之前，沙尘暴尚未开始，即所有建筑完全可见。

输入格式

第一行包含两个整数 $n$ 和 $q$ —— 建筑的数量和沙尘暴等级修改请求的数量（$1 \le n, q \le 10^5$）。

第二行包含 $n$ 个整数 $h_i$ —— 建筑的高度（$1 \le h_i \le 10^9$）。

接下来的 $q$ 行每行描述一个请求。第 $i$ 行包含三个整数 $l_i, r_i, f_i$ —— 沙尘暴等级发生变化的区间端点，以及新的等级（$1 \le l_i \le r_i \le n$；$0 \le f_i \le 10^9$）。

输出格式

输出 $q$ 行，每行一个整数 —— 对应请求的答案。

评分系统

仅当某子任务及其依赖子任务的所有测试均通过时，才可获得该子任务的分数。

样例

样例 1

输入

1 3
100
1 1 50
1 1 120
1 1 0

输出

50
100
0

样例 2

输入

4 5
1 5 7 3
1 3 1
2 4 2
2 3 5
1 4 3
3 4 100

输出

6
7
13
10
14