题目背景

戌蛤：最近在尝试买键盘

我：（然后呢

戌蛤：然后就买了其实……

戌蛤：但是还没到

戌蛤：所以又看了几个好看的

戌蛤：不过不可能再买了

戌蛤：毕竟我没有同时操纵两个键盘的特异功能

戌蛤：某学弟带了一个会发光的键盘

戌蛤：不过可以关掉

戌蛤：所以没有被 loli 奶

我：海星

题目描述

简单版本与常规版本唯一的区别在于：简单版本询问时针对整个序列，而常规版本询问时针对某个区间。

通过简单版本计 $1$ 分，通过常规版本计 $1$ 分，两个版本的分数相互独立。

给出一个序列。每次询问给出 $l, r, k$，要求找出 $[l, r]$ 的长度大于等于 $k$ 的所有子区间 $[x, y]$ 中 $\max\{a_x, a_{x + 1}, \dots, a_y\}$ 的最小值。强制在线。

输入输出格式

输入格式

输入数据的第一行包含两个正整数 $n, m$，分别表示序列长度和操作数量。

输入数据的第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示给出的序列。

输入数据的接下来 $m$ 行，每行包含三个正整数 $l, r, k$，表示一次询问。

同一行内的多个数字之间由空格隔开。其中 $l, r, k$ 需要异或上一次询问的答案 $\text{lastans}$ 来解密。首次询问之前 $\text{lastans}$ 的值为 $0$。

输出格式

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

输入输出样例

6 4
1 1 4 5 1 4
1 4 2
0 5 2
5 0 0
4 3 6

1
4
5
4

16 16
889160466 815488938 304206531 281907922 18485598 729244583 14546917 114700504 477138378 940043626 689020584 901227226 711613420 99627973 136092210 939758183 
1 14 9
889160464 889160471 889160467
18485593 18485590 18485596
114700508 114700488 114700499
940043621 940043621 940043627
136092213 136092216 136092209
477138376 477138375 477138383
729244577 729244587 729244577
940043628 940043616 940043627
14546922 14546933 14546916
136092213 136092194 136092214
901227225 901227216 901227231
729244587 729244586 729244582
711613415 711613408 711613421
689020589 689020579 689020589
729244585 729244585 729244582

889160466
18485598
114700504
940043626
136092210
477138378
729244583
940043626
14546917
136092210
901227226
729244583
711613420
689020584
729244583
99627973

样例解释

对于样例 #1，真实的输入数据如下：

6 4
1 1 4 5 1 4
1 4 2
1 4 3
1 4 4
1 6 3

对于样例 #2，真实的输入数据如下：

16 16
889160466 815488938 304206531 281907922 18485598 729244583 14546917 114700504 477138378 940043626 689020584 901227226 711613420 99627973 136092210 939758183 
1 14 9
2 5 1
7 8 2
4 16 11
15 15 1
7 10 3
2 13 5
6 12 6
6 10 1
15 16 1
7 16 4
3 10 5
12 13 1
11 12 1
5 11 5
14 14 1

数据范围与约定

$1 \leqslant n, m \leqslant 10^5$。$0 \leqslant a_i \leqslant 10^9$，$1 \leqslant l \leqslant r \leqslant n$，$1 \leqslant k \leqslant r - l + 1$。

时空限制：$\texttt{1s/256MiB}$。