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。