Вам задан массив 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 операций указанного вида. От Вас требуется выполнить все заданные операции, для каждого запроса суммы требуется вывести полученный результат.
Выходные данные
Для каждого запроса типа 1 в отдельной строке выведите сумму чисел на требуемом отрезке. Ответы на запросы выводите в том порядке, в котором они заданы во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|