XOR и единичные биты

Дан массив. Запросы: применить XOR с числом $x$ ко всем элементам отрезка и узнать суммарное количество единичных битов у всех чисел отрезка.

В первой строке $n$ и $m$ ($1 \le n, m \le 10^5$). Во второй — $n$ чисел $a_i$ ($0 \le a_i \le 10^6$). Далее $m$ строк: x l r v — XOR с $v$ на отрезке ($0 \le v \le 10^6$), или c l r — суммарное количество единичных битов.

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