考虑一个包含 $k$ 个整数的数组 $b_1, b_2, \dots, b_k$。令 $x \oplus y$ 表示 $x$ 和 $y$ 的按位异或运算。我们定义数组 $b$ 的线性幂（linear power）为：

$$LP(b) = \max_{i=0,1,\dots,k} ((b_1 \oplus \dots \oplus b_i) + (b_{i+1} \oplus \dots \oplus b_k))$$

给定一个包含 $n$ 个整数的数组 $a$，求其所有前缀的线性幂。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 10^6$)，表示数组的长度。 第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^6$)。

输出格式

输出一行，包含 $n$ 个由空格分隔的整数：$LP(a_1), LP(a_1, a_2), \dots, LP(a_1, a_2, \dots, a_n)$。

样例

输入 1

5
1 2 3 4 5

输出 1

1 3 6 10 9

输入 2

10
11 13 14 14 9 8 0 10 10 7

输出 2

11 24 20 24 15 23 23 17 23 30