P17629 永远的朋友

我还没问她在说什么，樽见就先抬起头。 「你这次要当我一辈子的朋友喔，小岛。」 樽见正在流泪。 是我害她流下了眼泪。 比冬天还要冰冷的某种东西降落在我的头顶上，穿过头发之间的空隙。 会因为维持朋友关系而哭，就表示── 脑袋一片混乱。 难道樽见也是吗？我本来想问她，喉咙却组织不出这句话。 「嗯。」 樽见用言语以外的方式传达的讯息，化成不多做停歇的风。这阵风跟河边的冰冷空气一同吹过我身上的细小空洞，留下轻微的疼痛。我的声音干燥到感觉不出任何水分。 这次要当我一辈子的── 朋友。

岛村想要给安达准备一些手工品当作礼物。 商场里面有 $n$ 种材料，它们分别有一个**特异值** $a_1,a_2,\ldots ,a_n$。 她想要为安达准备 $q$ 个礼物，其中第 $i$ 个礼物用商城中编号在区间 $[l_i,r_i]$ 中的所有材料制成，这 $(r_i-l_i+1)$ 份材料的**特异值**最初为 $[b_1,b_2,\cdots ,b_{r_i-l_i+1}]=[a_{l_i},a_{l_i+1},\cdots,a_{r_i}]$。 当然，她还要对材料进一步加工，以让礼物达到最完美的效果。准备第 $i$ 个礼物时，她用一个非负整数 $s_i$ 描述一个材料被加工后**特异值**的变化。具体来说，她可以对序列 $b$ 操作任意次，对于每次操作： - 选择一个整数 $1 \le p \le r_i-l_i+1$，然后将 $b_{p}$ 变为 $(b_{p} \operatorname{xor} s_i)$。 最后，她对礼物有两种评价标准： 1. $\mathrm{K}_1=b_{1} \operatorname{and} b_{2} \operatorname{and} \ldots \operatorname{and} b_{r_i-l_i+1}$。 2. $\mathrm{K}_2=b_{1} \operatorname{or} b_{2} \operatorname{or} \ldots \operatorname{or} b_{r_i-l_i+1}$。 她选择其中的第 $T$ 种，其中 $T \in \{1,2\}$ 给定，她想要知道 $\mathrm{K}_{T}$ 的可能达到的最大值。 她嫌这太麻烦了，你可以帮帮她吗？ 其中 $\operatorname{xor},\operatorname{and},\operatorname{or}$ 分别表示按位异或、按位与、按位或三种位运算。

第一行，一个数 $T$，表示岛村选择的礼物评价标准。 第二行，两个数 $n$ 和 $q$，分别表示商场的材料数量和礼物的数量。 第三行，$n$ 个数，依次表示商场材料的**特异值** $a_1 ,a_2,\ldots ,a_n$。 接下来 $q$ 行，对于其中的第 $i$ 行，有三个数，分别为 $l_i,r_i,s_i$，描述了第 $i$ 次询问。

由于某些原因，你只需要输出 $\sum_{i=1}^{q}(i\times \mathrm{ans}_i)$ 对 $2^{64}$ 取模的值。其中 $\mathrm{ans}_i$ 表示第 $i$ 次询问的答案。

### 样例解释 对于样例一，每组询问答案分别为 $16,32,20,16,1$。 对于样例二，每组询问答案分别为 $61,63,61,63,61$。 --- ### 数据范围 **本题目采用子任务捆绑测试。** 对于所有数据：$1 \le n,q \le 5 \times 10^5$，$T \in \{1,2\}$。 - $\forall 1 \le i \le n$，有 $0 \le a_i