← 返回题目列表

Codeforces · 587/E

E. 达夫作为女王

中文机器翻译题面 查看原题

Duff 是她的国家 Andarz Gu 的女王。她是一名竞技编程迷。这就是为什么当他看到她的部长马利克有空时,她给了她一个由n个非负整数a1,a2,...,an组成的序列,并要求他对这个序列执行q个查询。

有两种类型的查询:

1. 给定数字l、 r和k,Malek应该对每个l ≤ i ≤ r执行$$a_{i} = a_{i} \oplus k$$($$a \oplus b = a \text{xor} b$$,数字a和b的按位异或)。
2. 给定数字 l 和 r Malek 应该告诉她序列 al, al + 1, ..., ar 的分数。

序列 b1, ..., bk 的分数是其不同 Kheshtaks 的数量。非负整数 w 是该序列的 Kheshtak,当且仅当存在 b 的子序列时,我们将其表示为 bi1, bi2, ... , bix (可能为空),使得 $$w = b_{i_1} \oplus b_{i_2} \oplus \ldots \oplus b_{i_r}$$ (1 ≤ i1 < i2 < ... < ix ≤ k)。如果该子序列为空,则 w = 0。

与 Duff 不同,Malek 不是程序员。这就是为什么他请求你的帮助。请帮助他执行这些查询。

输入

输入的第一行包含两个整数 n 和 q(1 ≤ n ≤ 2 × 105 和 1 ≤ q ≤ 4 × 104)。

输入的第二行包含 n 个整数,a1, a2, ..., an,用空格分隔(对于每个 1 ≤ i ≤ n,0 ≤ ai ≤ 109)。

接下来的 q 行包含查询。每行以整数 t (1 ≤ t ≤ 2) 开头,对应查询的类型。如果 t = 1,则该行中还有三个整数:l、r 和 k。否则还有两个整数,l 和 r。 (1 ≤ l ≤ r ≤ n 且 0 ≤ k ≤ 109)

输出

在一行中打印第二类每个查询的答案。

示例

输入 #1

5 5
1 2 3 4 2
2 1 5
1 2 2 8
2 1 5
1 1 3 10
2 2 2

输出 #1

8
16
1

注意

在第一个查询中,我们想要序列 1, 2, 3, 4, 2 的所有 Kheshtaks,即:0, 1, 2, 3, 4, 5, 6, 7。

在第三个查询中,我们需要序列 1, 10, 3, 4, 2 的所有 Khestak,即:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15。

在第五个查询中,我们想要序列 0 的所有 Kheshtaks,即 0。