E. Совместимые числа
ограничение по времени на тест
4 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Два целых числа x и y называются совместимыми, если результат их побитового «И» равен нулю, то есть a & b = 0. Например, числа 90 (10110102) и 36 (1001002) совместимы, так как 10110102 & 1001002 = 02, а числа 3 (112) и 6 (1102) несовместимы, так как 112 & 1102 = 102.

Вам дан массив целых чисел a1, a2, ..., an. Требуется определить для каждого элемента массива, совместим ли этот элемент с каким-либо другим элементом из данного массива. В случае положительного ответа также требуется найти любой подходящей элемент.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 106) — количество элементов в данном массиве. Во второй строке через пробел записаны n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 4·106) — элементы данного массива. Числа в массиве могут повторяться.

Выходные данные

Выведите n целых чисел ansi. Если ai не совместимо ни с каким другим элементом данного массива a1, a2, ..., an, то ansi должно быть равно -1. Иначе ansi — любое такое число, что ai & ansi = 0, и при этом ansi содержится в массиве a1, a2, ..., an.

Примеры
Входные данные
2
90 36
Выходные данные
36 90
Входные данные
4
3 6 3 6
Выходные данные
-1 -1 -1 -1
Входные данные
5
10 6 9 8 2
Выходные данные
-1 8 2 2 8