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