Codeforces Round 731 (Div. 3) |
---|
Закончено |
Последовательность неотрицательных целых чисел $$$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$$$, то последовательность является растущей.
Например, следующие четыре последовательности являются растущими:
Следующие три последовательности не являются растущими:
Рассмотрим две последовательности неотрицательных чисел $$$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
Название |
---|