B. Подарок
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На восьмое марта Катерине подарили массив чисел. Со временем ей стало скучно просто смотреть на него, и она решила посчитать некоторые его бесполезные характеристики. Со всеми, что она придумывала, ей это удавалось. Придумав очередную — 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.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — количество чисел в массиве.

Вторая строка содержит целые числа $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$).

Выходные данные

Выведите одно число — xor попарных сумм чисел в данном массиве.

Примеры
Входные данные
2
1 2
Выходные данные
3
Входные данные
3
1 2 3
Выходные данные
2
Примечание

В первом примере есть всего одна сумма: $$$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$$$.