Co-growing Sequence
Contest: Codeforces Round 731 (Div. 3)
Difficulty rating: 1300
Tags: bitmasks, constructive algorithms, greedy

A sequence of non-negative integers $$$a_1, a_2, \dots, a_n$$$ is called growing if for all $$$i$$$ from $$$1$$$ to $$$n - 1$$$ all ones (of binary representation) in $$$a_i$$$ are in the places of ones (of binary representation) in $$$a_{i + 1}$$$ (in other words, $$$a_i \:\&\: a_{i + 1} = a_i$$$, where $$$\&$$$ denotes bitwise AND). If $$$n = 1$$$ then the sequence is considered growing as well.

For example, the following four sequences are growing:

- $$$[2, 3, 15, 175]$$$ — in binary it's $$$[10_2, 11_2, 1111_2, 10101111_2]$$$;
- $$$[5]$$$ — in binary it's $$$[101_2]$$$;
- $$$[1, 3, 7, 15]$$$ — in binary it's $$$[1_2, 11_2, 111_2, 1111_2]$$$;
- $$$[0, 0, 0]$$$ — in binary it's $$$[0_2, 0_2, 0_2]$$$.

The following three sequences are non-growing:

- $$$[3, 4, 5]$$$ — in binary it's $$$[11_2, 100_2, 101_2]$$$;
- $$$[5, 4, 3]$$$ — in binary it's $$$[101_2, 100_2, 011_2]$$$;
- $$$[1, 2, 4, 8]$$$ — in binary it's $$$[0001_2, 0010_2, 0100_2, 1000_2]$$$.

Consider two sequences of non-negative integers $$$x_1, x_2, \dots, x_n$$$ and $$$y_1, y_2, \dots, y_n$$$. Let's call this pair of sequences co-growing if the sequence $$$x_1 \oplus y_1, x_2 \oplus y_2, \dots, x_n \oplus y_n$$$ is growing where $$$\oplus$$$ denotes bitwise XOR.

You are given a sequence of integers $$$x_1, x_2, \dots, x_n$$$. Find the lexicographically minimal sequence $$$y_1, y_2, \dots, y_n$$$ such that sequences $$$x_i$$$ and $$$y_i$$$ are co-growing.

The sequence $$$a_1, a_2, \dots, a_n$$$ is lexicographically smaller than the sequence $$$b_1, b_2, \dots, b_n$$$ if there exists $$$1 \le k \le n$$$ such that $$$a_i = b_i$$$ for any $$$1 \le i < k$$$ but $$$a_k < b_k$$$.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — length of the sequence $$$x_i$$$.

The second line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i < 2^{30}$$$) — elements of the sequence $$$x_i$$$.

It is guaranteed that the sum of $$$n$$$ overall all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i < 2^{30}$$$) — lexicographically minimal sequence such that such that it's co-growing with given sequence $$$x_i$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
5
4
1 3 7 15
4
1 2 4 8
5
1 2 3 4 5
4
11 13 15 1
1
0

Example output:
0 0 0 0 
0 1 3 7 
0 1 0 3 2 
0 2 0 14 
0

Editorial:
In order to build lexicographically minimal co-growing with $$$x_i$$$ sequence, it is enough to build its elements iteratively, beginning from $$$y_1$$$ and minimizing the $$$i$$$-th element assuming that $$$y_1, \ldots, y_{i - 1}$$$ have already been found.
Assign $$$y_1 = 0$$$. According to the statement, all elements of the sequence are non-negative, so $$$y_1$$$ cannot be less than zero. It turns out that $$$y_i = 0$$$ is the minimal possible first element. The existence of an answer with $$$y_1 = 0$$$ follows from the construction algorithm described below.
Let's use mathematical induction and construct $$$y_i$$$ under the assumption that all the previous elements of the sequence have already been constructed. In order to satisfy the condition for the growth of the final sequence, the number $$$x_i \oplus y_i$$$ must contain one bits at all places (but not necessarily limited to them), on which there are one bits in the number $$$x_{i - 1} \oplus y_{i - 1}$$$. Let's denote $$$x_{i - 1} \oplus y_{i - 1}$$$ for $$$t$$$ and find out what bits can be in $$$y_i$$$ to satisfy this condition:
• If in $$$t$$$ stands $$$0$$$ bit then independently from $$$x_i$$$ in $$$y_i$$$ at the same spot we can place any bit because there is no limit on the corresponding bit in $$$x_i \oplus y_i$$$;
• If in $$$t$$$ stands $$$1$$$ bit and in $$$x_i$$$ — $$$0$$$ then the corresponding bit in $$$y_i$$$ should be equal $$$1$$$, so that in $$$x_i \oplus y_i$$$ the corresponding bit also equals one;
• If in $$$t$$$ and in $$$x_i$$$ stands $$$1$$$ bit then in $$$y_1$$$ should be $$$0$$$ bit at the corresponding place for the same reasons.
The bit transformation described above can be given by the expression $$$y_i = \left(t\,|\,x_i\right) \oplus x_i$$$. Indeed, this expression gives us bit 'one' at the fixed position if and only if at that place in $$$t$$$ stands $$$1$$$ bit and in $$$x_i$$$ stands $$$0$$$ bit. For the full solution, it remains only to apply this formula in a loop from $$$2$$$ to $$$n$$$.