e-olymp
Змагання

IOI 2019 Azerbaijan Team Selection Contest (Day1 + Day2)

XOR-ящий Мурад

Мурад очень любит операцию XOR. Он весь день, не переставая XOR-ит различные числа между собой.

В этот раз Мурад встретился с такой задачей. Ему дан массив a размера n. Мурад должен выполнить на этом массиве q запросов. Запросы, как показано ниже, бывают двух типов:

1) 1 l r - в этом запросе на промежутке [l, r] (1l < rn) нужно вычислить сумму всех попарных XOR-ов, то есть величину

xorimg.png

2) 2 l r v - в этом запросе на промежутке [l, r] (1lrn) нужно поXOR-ить все элементы с v.

Примечание: здесь XOR - побитовая операция xor.

Входные данные

В первой строке даны два числа n и q (2n2 * 105, 1q105) - размер массива и количество запросов соответственно. На следующей строке перечислены сами элементы массива ai (0ai109).

В следующих q строках даны сами запросы. Сначала идёт тип запроса, число 1 или 2. Если запрос 1 типа, то далее идут два числа l и r (1l < rn). Если запрос 2 типа, то далее идут три числа l, r и v (1lrn, 0v109).

Выходные данные

Вывести ответы на все запросы типа 1.

Ліміт часу 2 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3 3
1 2 3
1 1 3
2 1 3 2
1 1 2
Вихідні дані #1
6
3
Вхідні дані #2
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
Вихідні дані #2
30
15
26
49
Автор Rashad Mammadov
Джерело 2019 İOİ Отборочный тур сборной Азербайджана