XOR-ячий Мурад#9030
Мурад дуже захоплюється операцією XOR. Він проводить увесь день, виконуючи XOR над різними числами.
Цього разу Мурад зіткнувся з такою задачею. Йому дано масив розміру . Мурад повинен виконати запитів на цьому масиві. Запити бувають двох типів:
1 l r - у цьому запиті потрібно обчислити суму всіх попарних XOR-ів на проміжку [, ] (1 \leq l < r \leq n), тобто величину
2 l r v - у цьому запиті потрібно виконати операцію XOR з усіма елементами на проміжку [, ] (1 \leq l \leq r \leq n) з числом .
Примітка: тут XOR - це побітова операція xor.
У першому рядку подано два числа і (2 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 10^5) - розмір масиву та кількість запитів відповідно. У наступному рядку наведено елементи масиву a_i (0 \leq a_i \leq 10^9).
У наступних рядках подано самі запити. Спочатку йде тип запиту, число або . Якщо запит типу , то далі йдуть два числа і (1 \leq l < r \leq n). Якщо запит типу , то далі йдуть три числа , і (1 \leq l \leq r \leq n, 0 \leq v \leq 10^9).
Виведіть відповіді на всі запити типу .
Приклад 1
Приклад 2