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*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> 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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/27c8ed4094a545433bfe9d1b4f6bc07014c4c107.png" style="max-width: 100.0%;max-height: 100.0%;"/> for each *l* ≤ *i* ≤ *r* (<img align="middle" class="tex-formula" src="https://espresso.codeforces.com/a8613e6a61b972726c59753694d285066491bf22.png" style="max-width: 100.0%;max-height: 100.0%;"/>, bitwise exclusive OR of numbers *a* and *b*). 1.  given numbers *l* and *r* Malek should tell her the score of sequence *a*<sub class="lower-index">*l*</sub>, *a*<sub class="lower-index">*l* + 1</sub>, ... , *a*<sub class="lower-index">*r*</sub>. 
Score of a sequence *b*<sub class="lower-index">1</sub>, ..., *b*<sub class="lower-index">*k*</sub> 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*<sub class="lower-index">*i*<sub class="lower-index">1</sub></sub>, *b*<sub class="lower-index">*i*<sub class="lower-index">2</sub></sub>, ... , *b*<sub class="lower-index">*i*<sub class="lower-index">*x*</sub></sub> (possibly empty) such that <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/8cc97122f3f177bb22279df5b149ea93ef9f6978.png" style="max-width: 100.0%;max-height: 100.0%;"/> (1 ≤ *i*<sub class="lower-index">1</sub> &lt; *i*<sub class="lower-index">2</sub> &lt; ... &lt; *i*<sub class="lower-index">*x*</sub> ≤ *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<sup class="upper-index">5</sup> and 1 ≤ *q* ≤ 4 × 10<sup class="upper-index">4</sup>).

The second line of input contains *n* integers, *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> separated by spaces (0 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup> 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<sup class="upper-index">9</sup>)
import sys

def k_(a):
  if len(a) == 0:
    return [0]
  b = k_(a[1:])
  res = list()
  res.append(a[0])
  res.extend(b)
  for item in b:
    res.append(a[0] ^ item)
  return res

args = sys.stdin.readlines()
spl = args[0].split(" ")
n = int(spl[0])
q = int(spl[1])
spl = args[1].split(" ")
a = list()
for i in range(n):
  a.append(int(spl[i]))
for i in range(2, q+2):
  spl = args[i].split(" ")
  t = int(spl[0])
  if t == 1:
    l = int(spl[1])
    r = int(spl[2])
    k = int(spl[3])
    for j in range(l-1, r):
      a[j] = a[j] ^ k
  else:
    l = int(spl[1])
    r = int(spl[2])
    ks = dict()
    res = list(set(a[l-1:r]))
    if len(res) == 0:
      print(0)
    else:
      sss = k_(res)
      print(len(set(sss)))