题目描述

我们称 $x$ 是序列 $a$ 的一个子序列中的 Powerless Suffix Mode，当且仅当：

• $x$ 是该子序列的众数$^{\dagger}$。
• 不存在满足 $i < j$ 的下标 $i, j$ 使得 $a_i = a_j = x$ 且 $a_i$ 属于该子序列、$a_j$ 不属于该子序列。
• $x$ 在子序列中出现次数不超过 $x$ 在整个序列中出现次数的 $p\%$。

给定长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。给出 $q$ 次询问，每次询问给出整数 $l,r,p$（$1 \le l \le r \le n$，$1 \le p \le 100$），求序列 $b=[a_l,a_{l+1},\dots,a_{r-1},a_r]$ 所有非空子序列 Powerless Suffix Mode 的异或和（若某个子序列有多个 Powerless Suffix Mode 则全部异或，若没有则异或 $0$）。

注意，此时判定一个数是否是 Powerless Suffix Mode 的条件中，“整个序列”为序列 $b$。

---

$^{\dagger}$一个序列的众数是指序列中出现次数最多的数，一个序列可以有多个众数，例如序列 $[1,2,1,3,2]$ 的众数有 $1$ 和 $2$。

输入格式

第一行，两个整数 $n,q$。

第二行，$n$ 个整数 $a_1, \ldots, a_n$。

接下来 $q$ 行，每行三个整数 $l,r,p$，表示一次询问。

输出格式

对于每次询问，输出一行一个数，表示答案。

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

提示

【样例解释 #1】

为了方便说明，以下简称 Powerless Suffix Mode 为 PSM。

对于第一组询问，考察的序列是 $b=[1, 9, 1]$。该序列的非空子序列有 $[1]$、$[9]$、$[1]$、$[1,9]$、$[1,1]$、$[9,1]$、$[1,9,1]$。子序列 $[9]$ 的 PSM 是 $9$；子序列 $[1,9]$ 的众数是 $1$ 和 $9$，但是由于 $b_1=b_3=1$ 且 $b_1$ 在子序列中而 $b_3$ 不在，所以其中只有 $9$ 是 PSM。枚举可得，将所有子序列的 PSM 全部异或起来，最终结果为 $9$。

对于第二组询问，考察的序列是 $b=[4, 5, 1, 4]$。$p=50\%$ 的限制意味着，若一个数在子序列中成为 PSM，它的出现次数不能超过它在 $b$ 中出现次数的 $50\%$。例如，对于数 $4$，它在 $b$ 中出现 $2$ 次，那么在子序列中最多出现 $2\times 50\%=1$ 次。枚举可得，所有非空子序列的 PSM 的异或和为 $0$。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 $1\le n\le 2.5\times10^5$，$1\le q\le 2.5\times10^5$，$0\le a_i<2^{24}$，$1\le l\le r\le n$，$1 \le p\le100$。

各子任务特殊限制如下：

子任务编号	$n\le$	$q\le$	$a_i<$	分值
$1$	$18$	$20$	$2^{24}$	$7$
$2$	$500$			$11$
$3$	$5000$			$15$
$4$	$2.5\times10^5$	$2.5\times10^5$	$2$	$13$
$5$			$2^6$	$14$
$6$			$2^8$
$7$	$5\times10^4$		$2^{24}$
$8$	$2.5\times10^5$			$12$