题目描述

题目译自 JOISC 2016 Day3 T2「回転寿司」

给出一个有 $N$ 个点的环，环上各点有一个初始权值 $a_i$。

给出 $Q$ 个询问，每次询问给出一个区间 $[l,r]$ 和一个值 $A$，对于 $A$ 的变动定义如下（$r$ 可能会小于 $l$ 因为是环形）：

for (int i = l; i <= r; i++) 
    if (a[i] > A) 
        swap(a[i], A);

对于每个询问，回答遍历完区间 $[l,r]$ 后 $A$ 的最终值。

注：我们按逆时针方向在环上编号，并规定 $[l,r]$ 为从位置编号为 $l$ 的点逆时针遍历至位置编号为 $r$ 的点所经过点的集合。

---

输入格式

第一行包括两个数 $N$ 与 $Q$ 表示环的大小和询问的个数；
之后的 $N$ 行每行为一个整数，第 $i$ 个为 $a_i$；
之后的 $Q$ 行每行有三个整数 $l_i$、$r_i$、$A_i$，表示如上所示。

---

输出格式

输出包括 $Q$ 行，每行包括一个数，为变动结束后 $A_i$ 的值。

---

样例 1

输入

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

输出

7
9
8
7
8
6
5

过程解释：

• 第一回后，$a$ 数组长这样：$8, 5, 6, 4, 5, 9$，此时 $A=7$；
• 第二回后，$a$ 数组长这样：$8, 5, 6, 4, 4, 5$，此时 $A=9$；
• 第三回后，$a$ 数组长这样：$7, 5, 6, 4, 4, 5$，此时 $A=8$；
• 第四回后，$a$ 数组长这样：$2, 5, 6, 4, 4, 5$，此时 $A=7$；
• 第五回后，$a$ 数组长这样：$2, 5, 6, 4, 4, 5$，此时 $A=8$；
• 第六回后，$a$ 数组长这样：$2, 5, 5, 1, 4, 4$，此时 $A=6$；
• 第七回后，$a$ 数组长这样：$2, 5, 3, 1, 4, 4$，此时 $A=5$；

---

样例 2

输入

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

输出

7
5

---

样例 3

输入

10 10
19
5
8
17
14
3
9
10
7
6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3

输出

19
10
14
17
8
10
3
12
7
9

---

数据范围与提示

对于全部的数据：

• $1 \leq N \leq 4\times 10^{5}$
• $1 \leq Q \leq 25000$
• $1 \leq a_i \leq 10^{9}$
• $1 \leq l,r \leq N$
• $1 \leq A \leq 10^{9}$

具体子任务限制及得分情况如下表：

Subtask	限制	分数
1	$1 \leq N \leq 2000, 1 \leq Q \leq 2000$	5
2	$l=1, r=N$	15
3	无追加限制	80