XOR-ящий Мурад
XOR-ящий Мурад
Мурад очень любит операцию XOR. Он весь день, не переставая XOR-ит различные числа между собой.
В этот раз Мурад встретился с такой задачей. Ему дан массив a размера n. Мурад должен выполнить на этом массиве q запросов. Запросы, как показано ниже, бывают двух типов:
1) 1 l r - в этом запросе на промежутке [l, r] (1 ≤ l < r ≤ n) нужно вычислить сумму всех попарных XOR-ов, то есть величину
2) 2 l r v - в этом запросе на промежутке [l, r] (1 ≤ l ≤ r ≤ n) нужно поXOR-ить все элементы с v.
Примечание: здесь XOR - побитовая операция xor.
Входные данные
В первой строке даны два числа n и q (2 ≤ n ≤ 2 * 105
, 1 ≤ q ≤ 105
) - размер массива и количество запросов соответственно. На следующей строке перечислены сами элементы массива ai
(0 ≤ ai
≤ 109
).
В следующих q строках даны сами запросы. Сначала идёт тип запроса, число 1 или 2. Если запрос 1 типа, то далее идут два числа l и r (1 ≤ l < r ≤ n). Если запрос 2 типа, то далее идут три числа l, r и v (1 ≤ l ≤ r ≤ n, 0 ≤ v ≤ 109
).
Выходные данные
Вывести ответы на все запросы типа 1.
3 3 1 2 3 1 1 3 2 1 3 2 1 1 2
6 3
4 6 4 8 7 8 1 2 4 2 1 2 2 1 3 4 2 1 1 8 1 1 3 1 1 4
30 15 26 49