Permutation XOR Sequence Reconstruction

Consider a permutation \(\{p_1, p_2, \dots , p_n\}\) of the integers from \(1\) to \(n\). Its XOR-generated sequence \(\{b_1, b_2, \dots, b_{n-1}\}\) is defined by

[ b_i = p_i \oplus p_{i+1} ]

where \(\oplus\) denotes the bitwise XOR operation (in C++ the operator is ^).

You are given the integer \(n\) and the sequence \(\{b_i\}_{i=1}^{n-1}\). Your task is to reconstruct any permutation \(\{p_i\}\) that produces the given XOR sequence. It is guaranteed that at least one solution exists.

inputFormat

The first line contains an integer \(n\) (with \(2 \le n\le 10^5\)), which is the length of the permutation. The second line contains \(n-1\) space-separated non-negative integers \(b_1, b_2, \dots, b_{n-1}\), representing the XOR-generated sequence.

outputFormat

Output a single line with \(n\) space-separated integers \(p_1, p_2, \dots, p_n\) representing the reconstructed permutation.

sample

4
3 1 7

1 2 3 4