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

每个宇宙中都有 $n$ 个魔法苹果。尽管这些宇宙有很多相似之处，但它们之间仍存在细微的差别。第 $j$ 个宇宙中第 $i$ 个苹果的魔法值为 $a_i \oplus j$。这里 $\oplus$ 表示按位异或运算。

BaoBao 非常优柔寡断，他准备了 $q$ 个旅行计划。每个旅行计划可以用三个整数 $l, r$ 和 $k$ 来描述，这意味着 BaoBao 将前往编号从 $l$ 到 $r$（包含边界）的每个宇宙，并收集每个宇宙中 $n$ 个苹果里魔法值第 $k$ 小的那个苹果。

对于每个旅行计划，请帮助 BaoBao 计算他所收集苹果的魔法值之和。注意，旅行计划并不会真正从每个宇宙中移除苹果。也就是说，每个询问都是独立的。

输入格式

每个测试文件中只有一个测试用例。

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示每个宇宙中苹果的数量和计划的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{60}$)。

接下来的 $q$ 行中，第 $i$ 行包含三个整数 $l_i, r_i$ 和 $k_i$ ($0 \le l_i \le r_i < 2^{60}, 1 \le k_i \le n$)，表示第 $i$ 个旅行计划。

输出格式

对于每个旅行计划，输出一行，包含一个整数，表示该计划的答案。由于答案可能很大，请输出其对 998244353 取模的结果。

样例

输入 1

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

输出 1

4
23
720895450