E. XOR на отрезке, сумма на отрезке

3000 мс · 512 МБ · всё или ничего

Дан массив. Запросы: применить XOR с числом $x$ ко всем элементам отрезка и узнать сумму на отрезке.

Формат ввода

В первой строке $n$ ( $1 \le n \le 10^5$ ). Во второй — $n$ чисел $a_i$ ( $0 \le a_i \le 10^6$ ). В третьей — $m$ ( $1 \le m \le 10^5$ ). Далее $m$ строк: 1 l r — сумма на отрезке, или 2 l r x — применить XOR с $x$ на отрезке ( $1 \le x \le 10^6$ ).

Формат вывода

Для каждого запроса первого типа выведите сумму на отдельной строке.

Примеры

ввод

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

вывод

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.