You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

幻想岛是用人们的幻想构筑的异次元空间，里面有圣诞老人、金银岛、超人以及良心出题人之类的东西。Butters 因为特别擅长幻想，成为了幻想岛的救世主和创造神。

造物的原材料可以视为一个整数序列，Butters 选择一个区间作为一个数集，再选出该数集一个任意的子集异或起来得到$x$，他想知道一个区间可以产生多少不同的 $x$。除此之外，Butters 有时不满意当前的原材料，会选出一个区间，把它们全部异或上一个数。

请你帮他快速回答询问。

输入格式

第一行两个数$n,q$；

第二行$n$个整数$a_i$表示初始序列。接下来$q$行每行一个操作：

$1\ l\ r\ x$ 表示把区间$[l,r]$全体异或上$x$；

$2\ l\ r$询问$[l,r]$中的数能够表示的数的数量。

输出格式

输出共若干行，对于每个操作 2 输出一行答案。

输入样例

10 10

965 616 284 809 59 324 56 291 1005 428 

2 4 10

2 8 10

2 7 10

2 1 6

2 1 9

1 1 10 849

1 8 10 315

1 7 10 800

1 1 10 885

2 5 10

输出样例

64

8

16

64

256

64

数据范围

对于$10\%$的数据，$n,q\leq 10$；

对于$30\%$的数据，$n,q\leq 1000$；

另外$30\%$的数据，$n=2\times 10^5,q=40000$，且只有询问；

对于$100\%$的数据，$n=2\times 10^5,q=40000,l_i\leq r_i,0\leq a_i\leq 10^9$.