P13688 「DLESS-3」XOR and Powerless Suffix Mode

We define a value $x$ as a "Powerless Suffix Mode" of a subsequence of a given sequence $b$, with a parameter $p$, if and only if the following conditions are met: - $x$ is a mode of the subsequence (i.e., one of the most frequent elements). - Let the subsequence be formed by elements of $b$ at indices $w_1, w_2, \dots, w_k$, and let $w = \{w_1, w_2, \dots, w_k\}$. There do not exist indices $i, j$ (of the sequence $b$) such that $i < j$, $b_i = b_j = x$, $i \in w$, and $j \notin w$. - The number of occurrences of $x$ in the subsequence does not exceed $p\%$ of the total number of occurrences of $x$ in the entire sequence $b$. You are given a sequence $a$ of $n$ non-negative integers and $q$ queries. Each query provides three integers $l, r, p$. For each query, consider the subarray $b = a[l \dots r]$ as the base sequence. You need to calculate the XOR sum of all Powerless Suffix Modes over all subsequences of $b$. If a particular subsequence has multiple Powerless Suffix Modes, all of them should be included in the XOR sum.

The first line contains two integers, $n$ and $q$. The second line contains $n$ integers, representing the sequence $a$. Each of the next $q$ lines contains three integers, $l, r, p$, describing one query.

For each query, output a single integer on one line, representing the answer.

For all test cases, it is guaranteed that: - $1\le n\le 2.5\times10^5$ - $1\le q\le 2.5\times10^5$ - $0\le a_i