На восьмое марта Катерине подарили массив чисел. Со временем ей стало скучно просто смотреть на него, и она решила посчитать некоторые его бесполезные характеристики. Со всеми, что она придумывала, ей это удавалось. Придумав очередную — xor попарных сумм чисел в массиве, она поняла, что не может придумать, как посчитать её для большого массива, и попросила вас помочь. А вы сможете? Более формально, вам нужно посчитать
\(\) (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ \(\)
Запись \(x \oplus y\) обозначает битовый XOR чисел (т.е. \(x\) ^ \(y\) для многих современных языков программирования). Об этой операции вы можете прочитать по ссылке в Wikipedia: https://tiny.cc/34xykz.
Выходные данные
Выведите одно число — xor попарных сумм чисел в данном массиве.
Примечание
В первом примере есть всего одна сумма: \(1 + 2 = 3\).
Во втором примере есть три суммы: \(1 + 2 = 3\), \(1 + 3 = 4\), \(2 + 3 = 5\). В двоичной системе счисления это \(011_2 \oplus 100_2 \oplus 101_2 = 010_2\), то есть 2.
\(\oplus\) означает операцию побитового xor. Чтобы определить \(x \oplus y\) рассмотрим двоичную запись чисел \(x\) и \(y\). Скажем, что \(i\)-й бит результата равен 1, если ровно один из \(i\)-х битов \(x\) и \(y\) равен 1. В противном случае \(i\)-й бит результата равен 0. Например, \(0101_2 \, \oplus \, 0011_2 = 0110_2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 2
|
3
|
|
2
|
3
1 2 3
|
2
|