P14764 [Opoi 2025] CCD’s Not-So-Hard Problem

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.

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.**

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.

For each query, output the corresponding answer.

Sample before encryption: ```text 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