题目描述

定义一个可重集合 $S$ 的 $\operatorname{mex}$ 为不在可重集合 $S$ 中的最小非负整数。

Yuki 有 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。Yuki 需要你选择 $k$ 个数组成一个可重集合 $S$，求 $S$ 的 $\gcd$ 和 $\operatorname{mex}$ 的异或和的最大值。同时，她希望你对于 $k = 1, 2, \cdots, n$ 均求出答案。

其中可重集合 $S$ 的 $\gcd$ 表示可重集合 $S$ 中所有非 $0$ 数的约数中最大的那个。例如 $\gcd(\{6, 9\}) = 3$，$\gcd(\{0, 4, 6\}) = 2$。特殊地，定义任意多个 $0$ 的 $\gcd$ 为 $0$。

输入格式

第一行，一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）。

第二行，$n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \leq a_i \leq 10^6$）。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示 $k=i$ 时的答案。

样例

样例输入 1

5
0 1 3 5 6

样例输出 1

6 7 3 3 3

样例输入 2

8
0 0 1 1 5 10 15 18

样例输出 2

18 19 19 4 4 3 3 3

样例解释

对于第一组样例：

• $k=2$ 时，其中一种选数的方案为选择 $0$ 和 $6$，此时 $\gcd(0,6)=6$，$\operatorname{mex}(0,6)=1$，异或和为 $7$；
• $k=3$ 时，其中一种选数的方案为选择 $0,1,5$，此时 $\gcd(0,1,5)=1$，$\operatorname{mex}(0,1,5)=2$，异或和为 $3$。