题目描述

某计算中心中有 $n$ 台终端，第 $i$ 台终端拥有一个互不相同的非负整数标识 $w_i$。

系统需要将当前在线的终端进行分组。大多数终端会两两组成一组；若在线终端数量为奇数，则最后剩下的一台终端单独成组。

设当前尚未分组的终端标识构成集合 $S$。对于两个标识 $a,b$，定义它们的协同度为

其中 $[P]$ 在命题 $P$ 成立时取 $1$，否则取 $0$。两个终端组成一组时，该组的贡献值为

系统不断执行以下操作，直到 $S$ 为空：

• 若 $S=\{a\}$，则将该终端单独成组，这一组的贡献值为 $a$；
• 若 $|S|\ge 2$，则从中选择一对协同度最大的标识 $a,b$，将对应终端组成一组，并从 $S$ 中删除它们。若有多对终端的协同度同时达到最大值，任意选择其中一对都不会影响最终结果。

一次分组任务的总校验值，定义为所有小组贡献值的按位异或和。

任务开始前，恰好会有一台终端离线。对于每一种可能离线的终端，请分别求出其余 $n-1$ 台终端完成分组后的总校验值。

输入格式

第一行包含一个整数 $n$，表示终端数量。

第二行包含 $n$ 个互不相同的非负整数 $w_1,w_2,\ldots,w_n$，表示各终端的标识。

输出格式

输出一行，共包含 $n$ 个整数。第 $i$ 个整数表示第 $i$ 台终端离线后，其余终端分组得到的总校验值。

样例

样例输入 1

1
147744151

样例输出 1

0

样例输入 2

2
120712 120412

样例输出 2

120412 120712

样例输入 3

6
0 2 5 7 8 10

样例输出 3

14 12 7 5 6 4

样例解释 3

若第 $1$ 台终端离线，则系统按照如下方式分组：

$S=\{2,5,7,8,10\}$，其中标识 $2,10$ 的协同度为 $3$，达到当前最大值，该组贡献为 $(2\oplus 10)-1=7$；

$S=\{5,7,8\}$，其中标识 $5,7$ 的协同度为 $1$，达到当前最大值，该组贡献为 $(5\oplus 7)-1=1$；

$S=\{8\}$，该终端单独成组，贡献值为 $8$。

最终总校验值为 $7\oplus 1\oplus 8=14$。

若第 $2$ 台终端离线，则分组为 $\{0,8\},\{5,7\},\{10\}$，总校验值为 $((0\oplus 8)-1)\oplus ((5\oplus 7)-1)\oplus 10=12$。

数据范围与提示

对于测试点 1 $\sim$ 3 满足：$n\leq 700$。

对于测试点 4 $\sim$ 5 满足：$n$ 为 $2$ 的次幂，$w_i=i-1$。

对于测试点 6 $\sim$ 7 满足：$n=2^{15}-50,\ w_i<2^{15}$。

对于所有测试点满足：$1\leq n\leq 5\times 10^5,\ 0\leq w_i\leq 10^{18}$，且所有 $w_i$ 互不相同。