Запросы на анти-xor
Недавно наш тренер Этибар изобрел новую побитовую операцию, которую он назвал анти-xor. Теперь он предлагает вам решить задачу, связанную с этой операцией. Операция обозначается символом #.
Вам дано N чисел, и необходимо выполнить следующие операции:
1) Примените анти-xor с числом X ко всем целым числам в диапазоне от L до R. Этот запрос записывается как “1 L R X”.
2) Выведите сумму всех чисел в диапазоне от L до R. Этот запрос записывается как “2 L R”.
Предполагается, что все числа являются 20-битными целыми числами, поэтому операция анти-xor применяется только к последним 20 битам.
Входные данные
Вам дано целое число N (1 ≤ N ≤ 100000). На второй строке следуют N целых чисел (0 ≤ A_i ≤ 10^6). Следующая строка содержит количество запросов Q (1 ≤ Q ≤ 100000). Каждая из следующих Q строк представляет собой один из запросов указанных форматов.
Выходные данные
Для каждого запроса вида “2 L R” выведите в отдельной строке сумму всех целых чисел в диапазоне от L до R.