P8438 The Frozen Land.

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...

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: ```plain 17409488245517115276142322168576189279543123341138742779319865028602486509006138934460661849637882913598407636154209737260165754120014607177773359981826603801250947835120164061898414398808778383710734965109968348499255333743808806819897228289078158612425862653924618211976295200391819532525867722941969825549125083939679976935766582544161633553282536186214629150364929344059634288758125744444293077873038252037297534321132535122264070340053106750045495648216831484920706070567384926577457983022367155402606111730048301290388577089307478371008345014562035666767719162727651399592653244427923731578583241159510645308913474636528103155221748236303528072259108507905341048592541395827961771903417533241290874568077431363019042931482055932874814355268929594505880132227031337095583783793918280184860930087635658394839764586155196454253268266394562535661446268255101517600243362823434368473980088051436392198234023198989135142538928701481935979801475550928245044051159083872693810338480154137358569089360697894156 ``` and it actually took ```plain 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.

The first line contains a positive integer $n$. The second line contains $n$ natural numbers $a_1,a_2,\cdots,a_n$.

Output one line containing one natural number as required.

**This problem uses bundled testcases.** |Test Point ID|$n$|Score|Memory Limit|Subtask ID| |----|----|----|----|----| |$1\sim3$|$=20$|$10$|$\texttt{256MB}$|0| |$4\sim6$|$=25$|$40$|$\texttt{256MB}$|1| |$7\sim10$|$\le30$|$50$|$\texttt{8MB}$|2| 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