• 时间：4s
• 空间：1024M

题目描述

小哈尼是一位宇宙旅行者，穿梭于无穷多个平行宇宙之间。每个宇宙都有一个整数编号，编号从 $0$ 开始。 每个宇宙里都有 $n$ 个魔法苹果。虽然这些宇宙之间有很多相似之处，它们仍然有细微的不同。在第 $j$ 个宇宙里，第 $i$ 个魔法苹果的魔法能量值为 $a_i\oplus j$，这里 $\oplus$ 是按位异或运算。 小哈尼是一个优柔寡断的人，所以他准备了 $q$ 个旅行计划。每个旅行计划可以记为三个整数 $l,r$ 和 $k$，表示小哈尼将访问编号从 $l$ 到 $r$ 的每个宇宙（含两端），并从每个宇宙的 $n$ 个苹果里，收集魔法能量值第 $k$ 小的苹果。 对每个旅行计划，求小哈尼收集的苹果的魔法能量值之和。请注意，旅行计划不会真的把苹果从每个宇宙中拿走。也就是说，每次询问是独立的。

输入格式

从 travel.in 文件读入数据。

第一行输入两个整数 $n$ 和 $q$ 表示每个宇宙里苹果的数量以及旅行计划的数量。

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

对于接下来 $q$ 行，第 $i$ 行输入三个整数 $l_i$ , $r_i$ 和 $k_i$ 表示第 $i$ 个旅行计划。

输出格式

输出到 travel.out 文件。

每个旅行计划输出一行，包含一个整数表示答案。由于答案可能很大，请将答案对 $998244353$ 取模后输出。

样例

8 3
2 0 2 4 0 5 2 6
1 1 6
2 7 5
0 1048575 4

4
23
720895450

样例2

见选手下发目录下的 附加样例/travel/ex_travel2.in 和 附加样例/travel/ex_travel2.out 文件。

样例3

见选手下发目录下的 附加样例/travel/ex_travel3.in 和 附加样例/travel/ex_travel3.out 文件。

样例4

见选手下发目录下的 附加样例/travel/ex_travel4.in 和 附加样例/travel/ex_travel4.out 文件。

说明/提示

对于 $20\%$ 的测试点，$l_i=r_i$。

对于另外 $10\%$ 的测试点，$n=1$。

对于另外 $20\%$ 的测试点，$q=1$。

对于 $100\%$ 的测试点，$ 1 \leq n,q \leq 10^5, 1 \leq k_i \leq n，0 \leq a_i <2^{60},0 \leq l_i \leq r_i < 2^{60}$。