P14243 [CCPC 2024 Shandong I] 宇宙旅行

堡堡是一位宇宙旅行者，穿梭于无穷多个平行宇宙之间。每个宇宙都有一个整数编号，编号从 $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

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