C. Волшебные формулы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В Томской области очень любят волшебные формулы. Вот, например, несколько таких формул.

Пусть задана последовательность целых положительных чисел p1, p2, ..., pn. Тогда выпишем волшебные формулы:

Здесь «mod» обозначает операцию взятия остатка от деления.

Выражение означает применение побитовой операции xor (исключающее «ИЛИ») к целым числам x и y. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как «^», в Pascal — как «xor».

Волшебные формулы в Томской области очень любят, а вот считать их — не очень. Поэтому ваша задача по заданной последовательности p посчитать значение Q.

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

В первой строке входных данных задано единственное целое число n (1 ≤ n ≤ 106). В следующей строке заданы n целых чисел: p1, p2, ..., pn (0 ≤ pi ≤ 2·109).

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

В единственной строке выходных данных требуется вывести единственное целое число — значение Q.

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