A9975 | Duff as a Queen

Duff is the queen of her country, Andarz Gu. She's a competitive programming fan. That's why, when he saw her minister, Malek, free, she gave her a sequence consisting of $n$ non-negative integers, $a_{1},a_{2},...,a_{n}$ and asked him to perform $q$ queries for her on this sequence.

There are two types of queries:

1. given numbers $l,r$ and $k$ , Malek should perform  for each $l<=i<=r$ (, bitwise exclusive OR of numbers $a$ and $b$ ).
2. given numbers $l$ and $r$ Malek should tell her the score of sequence $a_{l},a_{l+1},...\ ,a_{r}$ .

Score of a sequence $b_{1},...,b_{k}$ is the number of its different Kheshtaks. A non-negative integer $w$ is a Kheshtak of this sequence if and only if there exists a subsequence of $b$ , let's denote it as $b_{i1},b_{i2},...\ ,b_{ix}$ (possibly empty) such that  ( $1<=i_{1}<i_{2}<...<i_{x}<=k$ ). If this subsequence is empty, then $w=0$ .

Unlike Duff, Malek is not a programmer. That's why he asked for your help. Please help him perform these queries.

The first line of input contains two integers, $n$ and $q$ ( $1<=n<=2×10^{5}$ and $1<=q<=4×10^{4}$ ).

The second line of input contains $n$ integers, $a_{1},a_{2},...,a_{n}$ separated by spaces ( $0<=a_{i}<=10^{9}$ for each $1<=i<=n$ ).

The next $q$ lines contain the queries. Each line starts with an integer $t$ ( $1<=t<=2$ ), type of the corresponding query. If $t=1$ , then there are three more integers in that line, $l,r$ and $k$ . Otherwise there are two more integers, $l$ and $r$ . ( $1<=l<=r<=n$ and $0<=k<=10^{9}$ )

Print the answer of each query of the second type in one line.