H. Феникс и биты
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Феникс любит играть с битами — особенно используя битовые операции AND, OR и XOR. У него есть $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ и $$$q$$$ запросов, каждый одного из следующих типов:

  1. заменить все числа $$$a_i$$$, для которых $$$l \le a_i \le r$$$, на $$$a_i$$$ AND $$$x$$$;
  2. заменить все числа $$$a_i$$$, для которых $$$l \le a_i \le r$$$, на $$$a_i$$$ OR $$$x$$$;
  3. заменить все числа $$$a_i$$$, для которых $$$l \le a_i \le r$$$, на $$$a_i$$$ XOR $$$x$$$;
  4. вывести количество различных чисел $$$a_i$$$, для которых $$$l \le a_i \le r$$$.

В каждом запросе Феникса $$$l$$$, $$$r$$$ и $$$x$$$ заданы. Заметим, что он рассматривает значения чисел, а не их индексы.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le q \le 10^5$$$) — количество чисел и количество запросов, соответственно.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{20}$$$) — числа, которые есть у Феникса в начале.

В следующих $$$q$$$ строках заданы запросы. Для каждого запроса, первое число в строке $$$t$$$ ($$$1 \le t \le 4$$$) — это тип запроса.

Если $$$t \in \{1, 2, 3\}$$$, то далее следуют три целых числа $$$l_i$$$, $$$r_i$$$ и $$$x_i$$$ ($$$0 \le l_i, r_i, x_i < 2^{20}$$$; $$$l_i \le r_i$$$).

В противном случае (если $$$t=4$$$), далее следуют два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i < 2^{20}$$$).

Гарантируется, что есть хотя бы один запрос, где $$$t=4$$$.

Выходные данные

Выведите ответ для каждого запроса четвертого типа ($$$t=4$$$).

Примеры
Входные данные
5 6
5 4 3 2 1
1 2 3 2
4 2 5
3 2 5 3
4 1 6
2 1 1 8
4 8 10
Выходные данные
3
2
1
Входные данные
6 7
6 0 2 3 2 7
1 0 4 3
2 6 8 4
4 0 7
3 2 5 3
1 0 1 2
4 0 3
4 2 7
Выходные данные
5
1
2
Примечание

В первом примере:

  • В первом запросе, $$$2$$$ заменяется на $$$2$$$ AND $$$2 = 2$$$, и $$$3$$$ заменяется на $$$3$$$ AND $$$2 = 2$$$. Множество чисел становится $$$\{1, 2, 4, 5\}$$$.
  • Во втором запросе, есть $$$3$$$ различных числа от $$$2$$$ по $$$5$$$: $$$2$$$, $$$4$$$ и $$$5$$$.
  • В третьем запросе, $$$2$$$ заменяется на $$$2$$$ XOR $$$3 = 1$$$, $$$4$$$ заменяется на $$$4$$$ XOR $$$3 = 7$$$, и $$$5$$$ заменяется на $$$5$$$ XOR $$$3 = 6$$$. Множество чисел становится $$$\{1, 6, 7\}$$$.
  • В четвертом запросе, есть $$$2$$$ различных числа от $$$1$$$ по $$$6$$$: $$$1$$$ и $$$6$$$.
  • В пятом запросе, $$$1$$$ заменяется на $$$1$$$ OR $$$8 = 9$$$. Множество чисел становится $$$\{6, 7, 9\}$$$.
  • В шестом запросе, есть одно различное число от $$$8$$$ по $$$10$$$: $$$9$$$.