시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB82228.571%

문제

В самой обычной школе в Ваканде на уроке арифметики сегодня проходят битовые операции с числами.

А именно, операции and и xor. Напомним, что битовая операция над двумя числами выполняется независимо по каждому биту. Таблицы истинности для операций and и xor выглядят следующим образом:

$x$ $y$ $x$ and $y$ $x$ xor $y$
$0$ $0$ $0$ $0$
$0$ $1$ $0$ $1$
$1$ $0$ $0$ $1$
$1$ $1$ $1$ $0$

В начале урока учитель написал на доске последовательность длины $n$ из чисел. Затем он просит учеников последовательно выполнять следующие операции:

  • Учитель сообщает число $x$. Ученики должны получить новую последовательность, применив операцию xor с числом $x$ ко всем элементам текущей последовательности.
  • Учитель сообщает число $x$. Ученики должны получить новую последовательность, применив операцию and с числом $x$ ко всем элементам текущей последовательности.
  • Учитель сообщает числа $l$ и $r$, и просит сообщить ему количество чисел в текущей последовательности, которые больше либо равны $l$ и меньше либо равны $r$.

Помогите ученикам ответить на все вопросы учителя правильно.

입력

В первой строке содержится два целых числа $n$ и $q$ --- количество чисел в последовательности, и количество операций, которое нужно выполнить ($1 \le n \le 100\,000$, $0 \le q \le 100\,000$). В следующей строке дано $n$ целых чисел $a_i$ --- элементы исходной последовательности ($0 \le a_i < 2^{20}$). В следующих $q$ строках дано описание операций. Если строка начинается со слова <<xor>>, то это операция первого типа, дальше в той же строке дано число $x$, и ученикам нужно заменить все элементы $cur_i$ текущей последовательности на $(cur_i$ xor $x)$ ($0 \le x < 2^{20}$). Если строка начинается со слова <<and>>, то это операция второго типа, дальше в той же строке дано число $x$, и ученикам нужно заменить все элементы $cur_i$ текущей последовательности на $(cur_i$ and $x)$ ($0 \le x < 2^{20}$). Если строка начинается с символа '?', то дальше даны два целых числа $l$ и $r$, ученикам нужно посчитать количество элементов текущей последовательности $cur_i$, таких что $l \le cur_i \le r$ ($0 \le l \le r < 2^{20}$).

출력

Для каждой операции третьего типа на новой строке выведите искомое количество чисел.

예제 입력 1

5 5
1 2 3 4 5
? 3 4
xor 1
? 1 2
and 2
? 1 3

예제 출력 1

2
1
2

노트

Пояснение к первому тесту.

После операции xor $1$, последовательность будет выглядеть следующим образом:

$0$, $3$, $2$, $5$, $4$

После операции and $2$, последовательность будет выглядеть следующим образом:

$0$, $2$, $2$, $0$, $0$