回转寿司
题号：NC53240
时间限制：C/C++/Rust/Pascal 9秒，其他语言18秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2016 Day3 T2 「回転寿司」
给出一个有N个点的环，环上各点有一个初始权值a_i。
给出Q个询问，每次询问给出一个区间[l,r]和一个值A，对于A的变动定义如下（r可能会小于l因为是环形）：
 
for(inti=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

备注:

对于全部的数据，。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2736