Задача про XOR

В рамках подготовки к чемпионату мира Кирилл придумал Ане задачу. Он написал N знаковых 32-битных чисел и попросил вычислить значение некоторого выражения S. Пусть a₁, …, a_N - все эти числа. Тогда выражение это

S = (a₁ xor a₂ xor … xor a_n) xor (b₁ xor b₂ xor … xor b_n-1),

где

b_i = F(a_i, a_i+1) xor F(a_i, a_i+2) xor … xor F(a_i, a_n).

В этой формуле под знаком xor понимается побитовое «исключающее или», а F(a, b) = x - 1, где x - максимальная степень двойки, на которую делится нацело a-b, если a ≠ b, и F(a, b) = -1, если a = b. Все операции xor выполняются слева направо, если скобки не указывают иной порядок.

Аня, как большая специалистка в области циклов, быстро написала требуемую программу, однако программа работала слишком долго. Чтобы лучше разобраться в этом вопросе, она попросила вас написать программу, которая бы укладывалась в отведенное время. Помогите ей это сделать.

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

В первой строке входного файла INPUT.TXT содержится число N (1 ≤ N ≤ 10⁵). В следующих N строках содержится N 32-битных знаковых целых чисел a_i по одному на строке.

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

В выходной файл OUTPUT.TXT выведите значение выражения.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]