#P18179. Cosmic Travel

Cosmic Travel

Cosmic Travel

BaoBao 是一名宇宙旅行者,可以在无穷多个平行宇宙之间穿梭。这些宇宙从 00 开始,用整数编号。

每个宇宙中都有 nn 个魔法苹果。第 jj 个宇宙中,第 ii 个苹果的魔力为

ai⊕j,a_i\oplus j,

其中 ⊕\oplus 表示按位异或。

BaoBao 准备了 qq 个旅行计划。每个计划由三个整数 l,r,kl,r,k 描述:他会访问编号为 l,l+1,…,rl,l+1,\ldots,r 的每一个宇宙,并在每个宇宙中收集魔力第 kk 小的苹果。

对每个计划,求收集到的苹果的魔力之和,对 998244353998244353 取模。

每个计划相互独立,不会真的从任何宇宙中删除苹果。苹果按个数参与排名,魔力相同的苹果仍分别计算。

输入格式

每个输入文件只有一组数据。

第一行两个整数 n,qn,q,分别表示每个宇宙中的苹果数和旅行计划数。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

接下来 qq 行,每行三个整数 li,ri,kil_i,r_i,k_i,表示一个计划。

输出格式

输出 qq 行,每行一个整数,表示对应计划的答案对 998244353998244353 取模的结果。

数据范围

  • 1≤n,q≤1051\le n,q\le10^5;
  • 0≤ai<2600\le a_i<2^{60};
  • 0≤li≤ri<2600\le l_i\le r_i<2^{60};
  • 1≤ki≤n1\le k_i\le n。

样例输入

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

样例输出

4
23
720895450