Количество совместимых чисел

Сложная

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 128 мегабайт

Два целых числа X и Y называются совместимыми, если результат их побитового «И» равен нулю, то есть X AND Y = 0. Например, числа 77 (1001101[2]) и 50 (110010[2]) совместимы, так как 1001101[2] AND 110010[2] = 0[2], а числа 3 (11[2]) и 6 (110[2]) несовместимы, так как 11[2] AND 110[2] = 10[2].

Вам дан массив целых чисел A[1], A[2],..., A[n]. Требуется определить для каждого элемента массива, количество совместимых элементов с ним в данном массиве.

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

В первой строке записано целое число n (1 ≤ n ≤ 10^5) - количество элементов в данном массиве. Во второй строке через пробел записаны n целых чисел A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 4 * 10^6) - элементы данного массива. Числа в массиве могут повторяться.

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

Выведите n целых чисел через пробел, то есть количество совместимых чисел для каждого i-го элемента массива.

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Ввод #3

Ответ #3

Примечание

В первом примере элемент A[1] совместим с элементом A[2], поэтому ответ: 1 1.

Во втором примере элемент A[1] совместим с элементами A[2], A[4], элемент A[2] совместим с элементами A[1], A[4], A[5], элемент A[3] совместим с элементом A[4], элемент A[4] совместим с элементами A[1], A[2], A[3], элемент A[5] совместим с элементом A[2], поэтому ответ: 2 3 1 3 1.

Отправки 59

Коэффициент принятия 5 %