题目背景

238 神教 #1

在古老的传说中，南极企鹅是全知全能的真神，它们能轻易做到任何我们做不到的事情。在南极洲的广袤大陆上，没有任何生物能对它们构成威胁。

所幸，神并不是高高在上，对尘世不屑一顾的。经常有果敢的人类来到这里，运气好的话，能和神结为挚友——这是幸运的，因为神不需要从你这里得到什么，而它的力量却会一直庇佑你，直到永远。

而你是一位探险家，对传说的内容十分向往。在经历了不知多久的苦索之后，你终于找到了些许神迹，并成功地找到了传说中的“神”。

——并且是两位，但是……

题目描述

神正在辅导孩子做数学题。在神批评孩子的心算结果从低到高第

17409488245517115276142322168576189279543123341138742779319865028602486509006138934460661849637882913598407636154209737260165754120014607177773359981826603801250947835120164061898414398808778383710734965109968348499255333743808806819897228289078158612425862653924618211976295200391819532525867722941969825549125083939679976935766582544161633553282536186214629150364929344059634288758125744444293077873038252037297534321132535122264070340053106750045495648216831484920706070567384926577457983022367155402606111730048301290388577089307478371008345014562035666767719162727651399592653244427923731578583241159510645308913474636528103155221748236303528072259108507905341048592541395827961771903417533241290874568077431363019042931482055932874814355268929594505880132227031337095583783793918280184860930087635658394839764586155196454253268266394562535661446268255101517600243362823434368473980088051436392198234023198989135142538928701481935979801475550928245044051159083872693810338480154137358569089360697894156

位就错了并且居然花了

0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000215055865

秒才算完的时候，神的孩子发现了你，并要求你来验算一遍。

你当然做不到，于是你请求缩小数据范围，而神同意了。神说，你是个勇敢的探险者，在把这道题算完之后，会与你成为朋友。

现在，你只需要解决的是这么一个问题了：

给定一个正整数 $n$ 和自然数序列 $a_1,a_2,\cdots,a_n$。你需要对每一个 $0\le S\le 2^n-1$，求出数 $S$ 的“权值”。

一个数 $S$ 的权值 $v(S)$ 的计算方式是：把它写成二进制，如果它从低到高第 $x$ 位为 $1$，就把答案异或（xor）上 $a_x$。

神不想刻意刁难你，他只希望你把所有 $v(S)$ 求出来之后，把答案分别乘上对应的 $S$，然后异或起来，取模 $2^{64}$ 再交给他就好了。

你心知这个问题是很好算的。但是你还是希望尽量快地把结果求出，以成为神的朋友。

那么，加油吧！

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个自然数 $a_1,a_2,\cdots,a_n$。

输出格式

一行一个自然数如题。

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

提示

本题采用捆绑测试。

数据点编号	$n$	分值	空间限制	子任务编号
$1\sim3$	$=20$	$10$	$\texttt{256MB}$	0
$4\sim6$	$=25$	$40$		1
$7\sim10$	$\le30$	$50$	$\texttt{8MB}$	2

对于 $100\%$ 的数据，$1\le n\le 30,0\le a_i\le 2^{64}-1$。

---

样例解释

用 $\bigoplus$ 表示 异或。

对于第一个样例，$\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$。

---

本题不需要刻意卡常，$\texttt{1.4s}$ 已经是出题人最大的善良了，如果还跑不过那基本就一定是算法不优了。