New Divide

$k$개의 정수 $b_1, b_2, \ldots, b_k$로 이루어진 배열을 생각하자. $x \oplus y$는 $x$와 $y$의 비트별 배타적 논리합이다. 배열 $b$의 선형 파워를 다음과 같이 정의한다.

$\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{.}$

$n$개의 정수로 이루어진 배열 $a$가 주어진다. $a$의 모든 접두사에 대한 선형 파워를 구하라.

첫째 줄에 배열의 길이인 양의 정수 $n$이 주어진다. ($1 \le n \le 10^6$)

둘째 줄에 $n$개의 정수 $a_i$가 주어진다. ($0 \le a_i \le 10^6$)

$mathit{LP} (a_1)$, $mathit{LP} (a_1, a_2)$, $\ldots$, $mathit{LP} (a_1, a_2, \ldots, a_n)$을 공백으로 구분하여 한 줄에 출력한다.