非负整数序列 $$$a_1, a_2, \dots, a_n$$$ 被称为增长,如果对于从 $$$1$$$ 到 $$$n - 1$$$ 的所有 $$$i$$$,$$$a_i$$$ 中的所有(二进制表示形式)都位于 $$$a_{i + 1}$$$ 中(二进制表示形式)的位置(在换句话说,$$$a_i \:\&\: a_{i + 1} = a_i$$$,其中$$$\&$$$ 表示按位与)。如果 $$$n = 1$$$ 则该序列也被认为是增长的。
例如,以下四个序列正在增长:
- $$$[2, 3, 15, 175]$$$ — 二进制为 $$$[10_2, 11_2, 1111_2, 10101111_2]$$$;
- $$$[5]$$$ — 二进制为 $$$[101_2]$$$;
- $$$[1, 3, 7, 15]$$$ — 二进制为 $$$[1_2, 11_2, 111_2, 1111_2]$$$;
- $$$[0, 0, 0]$$$ — 二进制为 $$$[0_2, 0_2, 0_2]$$$。
以下三个序列是非增长的:
- $$$[3, 4, 5]$$$ — 二进制为 $$$[11_2, 100_2, 101_2]$$$;
- $$$[5, 4, 3]$$$ — 二进制为 $$$[101_2, 100_2, 011_2]$$$;
- $$$[1, 2, 4, 8]$$$ — 二进制为 $$$[0001_2, 0010_2, 0100_2, 1000_2]$$$。
考虑两个非负整数序列 $$$x_1, x_2, \dots, x_n$$$ 和 $$$y_1, y_2, \dots, y_n$$$。如果序列 $$$x_1 \oplus y_1, x_2 \oplus y_2, \dots, x_n \oplus y_n$$$ 正在增长,其中 $$$\oplus$$$ 表示按位异或,我们称这对序列为共同增长。
给你一个整数序列 $$$x_1, x_2, \dots, x_n$$$。找到字典顺序最小的序列 $$$y_1, y_2, \dots, y_n$$$ 使得序列 $$$x_i$$$ 和 $$$y_i$$$ 共同生长。
序列 $$$a_1, a_2, \dots, a_n$$$ 按字典顺序小于序列 $$$b_1, b_2, \dots, b_n$$$ 如果存在 $$$1 \le k \le n$$$ 使得 $$$a_i = b_i$$$ 对于任何 $$$1 \le i < k$$$ 但 $$$a_k <b_k$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$x_i$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$0 \le x_i < 2^{30}$$$) — 序列 $$$x_i$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i < 2^{30}$$$) — 字典顺序最小序列,使其与给定序列 $$$x_i$$$ 共同增长。
示例
输入 #1
5 4 1 3 7 15 4 1 2 4 8 5 1 2 3 4 5 4 11 13 15 1 1 0
输出 #1
0 0 0 0 0 1 3 7 0 1 0 3 2 0 2 0 14 0