题目描述

给定一个长度为 $n$ 的序列 $a$ 和 $m$ 次询问，每次查询 $[l, r]$ 区间内第 $k$ 小的颜色。

出于某些原因，本题强制在线。

输入格式

第一行，两个整数 $n, m$。

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$。

接下来 $m$ 行，每行三个整数 $l', r', k'$。

设 $\text{last\_ans}$ 为上一个询问的答案，则 $l = (l' \operatorname{xor} \text{last\_ans}) \bmod n + 1，r = (r' \operatorname{xor} \text{last\_ans}) \bmod n + 1，k = (k' \operatorname{xor} \text{last\_ans}) \bmod (r - l + 1) + 1$。

注意：若 $l > r$ 则交换 $l, r$，若上一个询问的答案为 $-1$ 则 $\text{last\_ans} = 0$。

输出格式

$m$ 行，每行一个整数。若区间内的颜色数小于 $k$，输出 $-1$；否则，输出区间内第 $k$ 小的颜色。

10 5
3 1 5 6 4 2 2 2 8 5 
411557971 957829880 532263476
522520394 877151126 788213692
29996341 805744647 928415111
67170767 343566035 82131806
228050485 939669125 751397400

1
-1
2
2
2

数据范围

对于 $30\%$ 的数据，$1 \leq n, m \leq 10^3$；

对于另 $20\%$ 的数据，$1 \leq a_i \leq 10^4$；

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$1 \leq a_i \leq n$，$0 \leq l', r', k' < 2^{31}$。