| Codeforces Round 149 (Div. 2) |
|---|
| Закончено |
Вам задан массив a, состоящий из n целых чисел a1, a2, ..., an. С этим массивом разрешается выполнять две операции:
- Вычислить сумму текущих элементов массива на отрезке [l, r], то есть посчитать значение al + al + 1 + ... + ar.
- Применить операцию xor с заданным числом x к каждому элементу массива на отрезке [l, r], то есть выполнить
. Эта операция изменяет ровно r - l + 1 элементов массива.
Выражение 
означает применение побитовой операции xor к числам x и y. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как «^», в Pascal — как «xor».
Вам задан список из m операций указанного вида. От Вас требуется выполнить все заданные операции, для каждого запроса суммы требуется вывести полученный результат.
В первой строке задано целое число n (1 ≤ n ≤ 105) — размер массива. Во второй строке через пробел заданы целые числа a1, a2, ..., an (0 ≤ ai ≤ 106) — исходный массив.
В третьей строке задано целое число m (1 ≤ m ≤ 5·104) — количество операций с массивом. В i-ой из следующих m строк сперва записано целое число ti (1 ≤ ti ≤ 2) — тип i-го запроса. Если ti = 1, то это запрос суммы, если ti = 2, то это запрос на изменение элементов массива. Если i-ая операция типа 1, то далее следуют два целых числа li, ri (1 ≤ li ≤ ri ≤ n). Если i-ая операция типа 2, то далее следуют три целых числа li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106). Числа в строках разделены одиночными пробелами.
Для каждого запроса типа 1 в отдельной строке выведите сумму чисел на требуемом отрезке. Ответы на запросы выводите в том порядке, в котором они заданы во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
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
26
22
0
34
11
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
38
28
