题目背景

CCD 曾经做过一道难题：

但是这道题太难了，题面太长写不下，所以只好放一道不难题。

题目描述

给你一个长度为 $n$ 的序列，有 $q$ 次询问，每次查询 $[l,r]$ 中恰好出现 $k$ 次的最大数。无解输出 $0$。

强制在线。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

第三行一个正整数 $q$。

之后 $q$ 行，每行三个正整数 $l,r,k\ (l\leq r)$。

本题强制在线，每次查询输入的所有数要 xor 上 $lastans$ 进行解密，第一次询问默认 $lastans=0$。

输出格式

对于每次询问，输出对应的答案。

10
8 3 1 3 1 3 1 1 1 8 
10
1 5 1
13 1 13
8 8 1
0 8 5
2 5 2
2 7 7
6 7 1
2 10 2
9 10 10
6 10 3

8
0
1
0
3
0
3
8
0
1

提示

加密前的样例：

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

本题采用捆绑测试。

$$\def\arraystretch{1.2} \begin{array}{|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline \end{array} & \begin{array}{c} n,q\\\hline \le 10^4\\\hline \le 5\times10^4\\\hline \end{array} & \begin{array}{c} \tt{pts}\\\hline 20\\\hline 80\\\hline \end{array} \\\hline \end{array}$$

对于所有数据，$1\leq k,a_i\leq n\leq 5\times10^4$，$1\leq q\leq 5\times10^4$。