Description

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.

Input Format

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.

Output Format

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

13 6
1 1 4 5 1 4 1 9 1 9 8 1 0
7 9 100
3 6 50
7 11 100
7 11 99
1 3 100
2 4 100

9
0
8
0
4
0

18 1
1 1 1 1 1 1 2 2 2 2 2 2 4 4 4 4 4 4
1 18 40

7

Hint

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<2^{24}$
• $0<p\le100$
• $1\le l\le r\le n$

This problem uses subtasks for scoring. The descriptions of the subtasks are as follows: