Mas的童年

时间限制 : 1 s

空间限制 : 1 gigabyte

题目

Mas完成了一天的工作，走在回家的路上，看着路边的景色，他想起来自己的童年。

许许多多的记忆交错，丝丝缕缕的牵扯着Mas。

在回忆的深处，Mas想起来了一个常常在幼儿园玩的游戏。

有$n$个小朋友一起排成一排，然后小朋友们会一起开始跳舞。

聪明的Mas发现，每个小朋友都有自己的高兴程度，对于第$i$个小朋友，他的高兴程度是$a_i$。

当一排高兴程度分别为$b_1,b_2,\dots,b_k$的$k$个小朋友跳舞的时候，他们会产生$b_1\oplus b_2\oplus\dots\oplus b_k$的愉悦值。

但是Mas觉得不够尽兴，于是他决定让小朋友们从某个位置分开，让原本一排的队伍分成两排，从而使两排新队伍的愉悦值加起来最大，当然，是有可能不分成两排的。

具体的，对于一排$k$个小朋友，他们的高兴程度分别是$b_1,b_2,\dots,b_k$，Mas会找到位置$i\in[0,k)$，使得$(b_1\oplus\dots\oplus b_i)+(b_{i+1}\oplus\dots\oplus b_k)$最大。

回想起这个游戏的Mas决定再来玩一下这个游戏，于是他想起来了某一天排成一排的$n$个小朋友的高兴程度$a_1,a_2,\dots,a_n$，对于$i=1..n$，Mas希望求出前$i$个小朋友排成的队伍中通过拆分成两个队伍能够得到的最大愉悦值的和是多少。

输入

第一行一个正整数$n$表示小朋友的数量。

第二行$n$个整数，表示$a_{1..n}$。

输出

一行$n$个整数表示答案。

样例输入&样例输出

见下发文件中的$childhood0$\sim$1.in$和$childhood0$\sim$1.ans$。

点此下载

数据范围

对于$30\%$的测试数据，$n\le 5000$

对于另外$40\%$的测试数据，$n\le 10^5,0\le a_i\le 10^5$

对于$100\%$的测试数据，$n\le 10^6,0\le a_i\le 10^6$