题目描述

堡堡是一位宇宙旅行者，穿梭于无穷多个平行宇宙之间。每个宇宙都有一个整数编号，编号从 $0$ 开始。

每个宇宙里都有 $n$ 个魔法苹果。虽然这些宇宙之间有很多相似之处，它们仍然有细微的不同。在第 $j$ 个宇宙里，第 $i$ 个魔法苹果的魔法能量值为 $a_i\oplus j$，这里 $\oplus$ 是按位异或运算。

堡堡是一个优柔寡断的人，所以他准备了 $q$ 个旅行计划。每个旅行计划可以记为三个整数 $l$，$r$ 和 $k$，表示堡堡将访问编号从 $l$ 到 $r$ 的每个宇宙（含两端），并从每个宇宙的 $n$ 个苹果里，收集魔法能量值第 $k$ 小的苹果。

对每个旅行计划，求堡堡收集的苹果的魔法能量值之和。请注意，旅行计划不会真的把苹果从每个宇宙中拿走。也就是说，每次询问是独立的。

输入格式

每个测试文件仅有一组测试数据。

第一行输入两个整数 $n$ 和 $q$（$1\leq n, q\leq 10^5$）表示每个宇宙里苹果的数量以及旅行计划的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$0\leq a_i<2^{60}$）。

对于接下来 $q$ 行，第 $i$ 行输入三个整数 $l_i$, $r_i$ 和 $k_i$（$0\leq l_i\leq r_i<2^{60}$，$1\leq k_i\leq n$）表示第 $i$ 个旅行计划。

输出格式

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

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

4
23
720895450