시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB17111066.667%

문제

Consider an array of $k$ integers $b_1, b_2, \ldots, b_k$. Let $x \oplus y$ be the bitwise exclusive OR of $x$ and $y$. We shall say the linear power of the array $b$ is $$\mathit{LP} (b) = \max\limits_{i = 0, 1, \ldots, k} (b_1 \oplus \ldots \oplus b_i) + (b_{i + 1} \oplus \ldots \oplus b_k)\text{.}$$

You are given an array $a$ of $n$ integers. Find the linear power of all its prefixes.

입력

The first line contains a positive integer $n$ ($1 \le n \le 10^6$), the length of the array.

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^6$).

출력

Output a single line containing $n$ space-separated integers: $\mathit{LP} (a_1)$, $\mathit{LP} (a_1, a_2)$, $\ldots$, $\mathit{LP} (a_1, a_2, \ldots, 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