Урок арифметики

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

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

В начале урока учитель написал на доске последовательность длины $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}$).

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

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

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

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

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

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