Background

238 Divine Cult #1.

In ancient legends, Antarctic penguins are all-knowing and all-powerful true gods. They can easily do anything we cannot, and on the vast continent of Antarctica, no creature can pose any threat to them.

Fortunately, gods are not always lofty and indifferent to the mortal world. Brave humans often come here, and if you are lucky, you may become close friends with a god. This is a blessing, because a god needs nothing from you, yet its power will keep protecting you forever.

You are an explorer who longs for these legends. After an unknown amount of hardship and searching, you finally found some traces of divine miracles and successfully found the legendary “god”.

—And there are two of them, but...

Problem Description

The gods are tutoring their child on a math problem. When the god criticized the child for getting the following digit (counting from low to high) wrong:

17409488245517115276142322168576189279543123341138742779319865028602486509006138934460661849637882913598407636154209737260165754120014607177773359981826603801250947835120164061898414398808778383710734965109968348499255333743808806819897228289078158612425862653924618211976295200391819532525867722941969825549125083939679976935766582544161633553282536186214629150364929344059634288758125744444293077873038252037297534321132535122264070340053106750045495648216831484920706070567384926577457983022367155402606111730048301290388577089307478371008345014562035666767719162727651399592653244427923731578583241159510645308913474636528103155221748236303528072259108507905341048592541395827961771903417533241290874568077431363019042931482055932874814355268929594505880132227031337095583783793918280184860930087635658394839764586155196454253268266394562535661446268255101517600243362823434368473980088051436392198234023198989135142538928701481935979801475550928245044051159083872693810338480154137358569089360697894156

and it actually took

0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000215055865

seconds to finish, the child noticed you and asked you to verify the calculation once.

Of course you cannot do that, so you asked to reduce the constraints, and the gods agreed. The gods said that you are a brave explorer, and after you finish this problem, they will become your friend.

Now you only need to solve the following problem:

Given a positive integer $n$ and a sequence of natural numbers $a_1,a_2,\cdots,a_n$. For every $0\le S\le 2^n-1$, compute the “weight” of the number $S$.

The weight $v(S)$ of a number $S$ is computed as follows: write $S$ in binary. If its $x$-th bit (from low to high) is $1$, then xor the answer with $a_x$.

The gods do not want to make things hard on purpose. After you compute all $v(S)$, they only ask you to multiply each value by its corresponding $S$, then xor everything together, take the result modulo $2^{64}$, and give it to them.

You know this problem is very easy to compute. Still, you hope to get the result as fast as possible, to become friends with the gods.

So, do your best.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ natural numbers $a_1,a_2,\cdots,a_n$.

Output Format

Output one line containing one natural number as required.

4
1 2 3 4

16

30
15942549000714163495 14973783748924019241 11750608274629447103 3841514779926491634 1491087352666302822 3926467265136890882 2165405652723005667 16850040541486744638 9389207531715430944 2453094189961991688 17306424574086088540 4253088488420240522 6711268779219669357 7357305029308027009 10742286389669332463 16939477641403891687 14194800553999397870 17414698597200046696 18113730556943709454 3735103125227126629 16235879363688955717 14861602169195639258 903677597641043180 12364536150445169736 14881735759803865853 14781978421412291657 872796319752083876 11301016179769629644 14385296580178382407 3946726419982234649 

13929368580789239808

Hint

This problem uses bundled testcases.

For $100\%$ of the testdata, $1\le n\le 30,0\le a_i\le 2^{64}-1$.

Sample Explanation

Use $\bigoplus$ to denote xor.

For the first sample, $\text{Ans}=(0\times 0)\bigoplus(1\times 1)\bigoplus(2\times 2)\bigoplus(3\times 3)\bigoplus(4\times 3)\bigoplus(5\times 2)\bigoplus(6\times 1)\bigoplus(7\times 0)\bigoplus(8\times 4)\bigoplus(9\times 5)\bigoplus(10\times 6)\bigoplus(11\times 7)\bigoplus(12\times 7)\bigoplus(13\times 6)\bigoplus(14\times 5)\bigoplus(15\times 4)=16$.

There is no need to deliberately optimize constants for this problem. $\texttt{1.4s}$ is already the biggest kindness from the problem setter. If you still cannot pass, then your algorithm is basically not good enough.

Translated by ChatGPT 5