Background

CCD once made a hard problem:

But that problem was too hard, and the statement was too long to fit, so we put a not-so-hard problem instead.

Problem Description

You are given a sequence of length $n$ and $q$ queries. For each query $[l, r]$, find the largest number that appears exactly $k$ times in $[l, r]$. If there is no solution, output $0$.

Forced online.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_i$.

The third line contains a positive integer $q$.

Then follow $q$ lines, each containing three positive integers $l, r, k\ (l \leq r)$.

This problem is forced online. For each query, all input numbers must be decrypted by xoring with $lastans$. For the first query, $lastans = 0$ by default.

Output Format

For each query, output the corresponding answer.

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

Hint

Sample before encryption:

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

This problem uses bundled testdata.

$$\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}$$

Constraints: For all data, $1 \leq k, a_i \leq n \leq 5\times10^4$, and $1 \leq q \leq 5\times10^4$.

Translated by ChatGPT 5