Мурад очень любит операцию XOR. Он весь день, не переставая XOR-ит различные числа между собой.
В этот раз Мурад встретился с такой задачей. Ему дан массив a размера n. Мурад должен выполнить на этом массиве q запросов. Запросы, как показано ниже, бывают двух типов:
1 l r - в этом запросе на промежутке [l, r] (1 ≤ l < r ≤ n) нужно вычислить сумму всех попарных XOR-ов, то есть величину
2 l r v - в этом запросе на промежутке [l, r] (1 ≤ l ≤ r ≤ n) нужно поXOR-ить все элементы с 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.