Statement is not available in English language
E. Модница
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нюша — большая модница и поклонница косметики. В её коллекции сотни баночек с пудрами, помадами и кремами. Перед каждой прогулкой с Барашем она наносит макияж, чтобы подчеркнуть свою элегантность.

Как известно любой моднице, не все косметические средства хорошо сочетаются друг с другом. Чтобы навести порядок в своей огромной коллекции, Нюша расставила всю косметику в один длинный ряд. Каждой баночке $$$i$$$ она сопоставила целое число $$$a_i$$$ — числовую характеристику её стиля.

Нюша придумала особое правило для оценки сочетаемости средств: для любого набора баночек она вычисляет так называемое магическое число — результат операции XOR ($$$\oplus$$$, побитовое исключающее ИЛИ) над всеми числами в этом наборе.

Что такое XOR?

XOR — это особая операция над числами. Чтобы её выполнить, нужно:

  • записать числа в двоичной системе (с одинаковым числом цифр, добавляя нули слева при необходимости);
  • в каждом разряде сравнить цифры:
    • если цифры одинаковые ($$$0$$$ и $$$0$$$ или $$$1$$$ и $$$1$$$) — пишем $$$0$$$;
    • если разные ($$$0$$$ и $$$1$$$) — пишем $$$1$$$.

Например:

$$$5$$$=$$$101_2$$$
$$$3$$$=$$$011_2$$$
$$$5\oplus 3$$$ = $$$6$$$=$$$110_2$$$

Для трёх и более чисел XOR вычисляется по шагам: сначала XOR первых двух, потом XOR результата с третьим и так далее.

В большинстве языков программирования операция XOR записывается с помощью символа «крышка». Например, в Python, C++ или Java выражение a ^ b означает побитовое исключающее ИЛИ чисел a и b.

Поскольку ряд косметики получился очень длинным, для одного макияжа Нюша решила использовать только средства, стоящие подряд, то есть некоторый подотрезок в этом ряду. Прогулок с Барашем предстоит много, и Нюша хочет каждый раз выглядеть по-новому.

Нюша хочет рассмотреть все возможные подотрезки (все способы выбрать подряд идущие баночки), вычислить магическое число для каждого из них, а затем найти XOR всех этих магических чисел. Помогите Нюше найти это итоговое число!

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

В первой строке находится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество косметических средств.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числовые характеристики стиля средств.

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

Выведите одно целое число — XOR магических чисел всех подотрезков.

Система оценки

В задаче 50 тестов, каждый оценивается на 2 балла. Тесты разбиты на 3 группы, внутри каждой группы действует потестовая оценка, то есть баллы начисляются за каждый тест независимо. Зависимости между группами тестов указаны в таблице ниже

ГруппаОграниченияБаллыЗависимые группы
$$$0$$$Тесты из условия$$$0$$$
$$$1$$$$$$1 \le n \le 100$$$$$$ 30$$$$$$0$$$
$$$2$$$$$$1 \le n \le 5000$$$$$$ 30$$$$$$0, 1$$$
$$$3$$$$$$1 \le n \le 2 \cdot 10^5$$$$$$ 40$$$$$$0, 1, 2$$$
Примеры
Входные данные
3
1 2 3
Выходные данные
2
Входные данные
5
1 3 4 5 2
Выходные данные
7
Входные данные
9
13 15 134 20 11 142 64 32 10
Выходные данные
202
Примечание

Разберём первый пример: массив $$$[1, 2, 3]$$$.

Все подотрезки и их магические числа:

  • $$$[1]$$$: $$$1$$$
  • $$$[2]$$$: $$$2$$$
  • $$$[3]$$$: $$$3$$$
  • $$$[1,2]$$$: $$$1 \oplus 2 = 3$$$
  • $$$[2,3]$$$: $$$2 \oplus 3 = 1$$$
  • $$$[1,2,3]$$$: $$$1 \oplus 2 \oplus 3 = 0$$$
Теперь вычислим XOR всех этих значений: $$$$$$ 1 \oplus 2 \oplus 3 \oplus 3 \oplus 1 \oplus 0 = 2. $$$$$$

Ответ: $$$2$$$.