CF587E Duff as a Queen

Duff 是她所在国家 Andarz Gu 的女王。她是一个竞赛编程的爱好者。因此，当她看到她的部长 Malek 有空时，给了他一个由 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ 组成的序列，并要求他在这个序列上执行 $q$ 个查询。  查询有两种类型： 1. 给定数字 $l, r$ 和 $k$，Malek 需要对每个 $l \leq i \leq r$ 执行 $a_i := a_i \oplus k$（$\oplus$ 表示按位异或运算）。 2. 给定数字 $l$ 和 $r$，Malek 需要告诉 Duff 序列 $a_l, a_{l+1}, \ldots, a_r$ 的得分。 一个序列 $b_1, b_2, \ldots, b_k$ 的得分是其不同 Kheshtak 的个数。对于该序列，非负整数 $w$ 是其 Kheshtak 当且仅当存在其某个子序列 $b_{i_1}, b_{i_2}, \ldots, b_{i_x}$（可为空），满足 $w = b_{i_1} \oplus b_{i_2} \oplus \ldots \oplus b_{i_x}$（$1 \leq i_1 < i_2 < \ldots < i_x \leq k$，可 $x=0$）。如果子序列为空，则 $w=0$。 与 Duff 不同，Malek 不是程序员。因此他向你求助。请帮助他完成这些查询。

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 2 \times 10^5$，$1 \leq q \leq 4 \times 10^4$）。 第二行包含 $n$ 个整数，分别为 $a_1, a_2, ..., a_n$，用空格分隔（$0 \leq a_i \leq 10^9$，$1 \leq i \leq n$）。 接下来的 $q$ 行，每行描述一个查询。每行首先是一个整数 $t$（$1 \leq t \leq 2$），表示查询类型。如果 $t=1$，则该行接着三个整数 $l$，$r$ 和 $k$。否则，接着两个整数 $l$ 和 $r$。（$1 \leq l \leq r \leq n$，$0 \leq k \leq 10^9$）

对于每个第二种类型（$t=2$）的查询，输出一行答案。

在第一个查询中，我们要求序列 $1,2,3,4,2$ 的所有 Kheshtak，为：$0,1,2,3,4,5,6,7$。 在第三个查询中，我们要求序列 $1,10,3,4,2$ 的所有 Kheshtak，为：$0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15$。 在第五个查询中，序列仅有 $0$，其所有 Kheshtak 只有 $0$。 由 ChatGPT 5 翻译