Последовательность неотрицательных целых чисел \(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\).
Выходные данные
Для каждого набора данных выведите \(n\) целых чисел \(y_1, y_2, \dots, y_n\) (\(0 \le y_i < 2^{30}\)) — лексикографически минимальную последовательность, которая является взаимнорастущей с заданной последовательностью \(x_i\).