极寒之地

神正在辅导孩子做数学题。在神批评孩子的心算结果从低到高第 ```plain 17409488245517115276142322168576189279543123341138742779319865028602486509006138934460661849637882913598407636154209737260165754120014607177773359981826603801250947835120164061898414398808778383710734965109968348499255333743808806819897228289078158612425862653924618211976295200391819532525867722941969825549125083939679976935766582544161633553282536186214629150364929344059634288758125744444293077873038252037297534321132535122264070340053106750045495648216831484920706070567384926577457983022367155402606111730048301290388577089307478371008345014562035666767719162727651399592653244427923731578583241159510645308913474636528103155221748236303528072259108507905341048592541395827961771903417533241290874568077431363019042931482055932874814355268929594505880132227031337095583783793918280184860930087635658394839764586155196454253268266394562535661446268255101517600243362823434368473980088051436392198234023198989135142538928701481935979801475550928245044051159083872693810338480154137358569089360697894156 ``` 位就错了并且居然花了 ```plain 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}$ 再交给他就好了。 你心知这个问题是很好算的。但是你还是希望尽量快地把结果求出，以成为神的朋友。 那么，加油吧！ ## Input 第一行一个正整数 $n$。 第二行 $n$ 个自然数 $a_1,a_2,\cdots,a_n$。 ## Output 一行一个自然数如题。 [samples] ## Background 238 神教 #1 在古老的传说中，南极企鹅是全知全能的真神，它们能轻易做到任何我们做不到的事情。在南极洲的广袤大陆上，没有任何生物能对它们构成威胁。 所幸，神并不是高高在上，对尘世不屑一顾的。经常有果敢的人类来到这里，运气好的话，能和神结为挚友——这是幸运的，因为神不需要从你这里得到什么，而它的力量却会一直庇佑你，直到永远。 而你是一位探险家，对传说的内容十分向往。在经历了不知多久的苦索之后，你终于找到了些许神迹，并成功地找到了传说中的“神”。 ——并且是两位，但是…… ## Note **本题采用捆绑测试。** |数据点编号|$n$|分值|空间限制|子任务编号| |----|----|----|----|----| |$1\sim3$|$=20$|$10$|$\texttt{256MB}$|0| |$4\sim6$|$=25$|$40$|$\texttt{256MB}$|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}$ 已经是出题人最大的善良了，如果还跑不过那基本就一定是算法不优了。