D. Взаимнорастущая последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$ называется растущей, если для всех $$$i$$$ от $$$1$$$ до $$$n - 1$$$ в двоичной записи $$$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$$$ является операцией побитового исключающего ИЛИ (то есть XOR).

Задана последовательность целых чисел $$$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$$$, что для любых $$$1 \le i < k$$$ выполнено $$$a_i = b_i$$$, но $$$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$$$.

Пример
Входные данные
5
4
1 3 7 15
4
1 2 4 8
5
1 2 3 4 5
4
11 13 15 1
1
0
Выходные данные
0 0 0 0 
0 1 3 7 
0 1 0 3 2 
0 2 0 14 
0