Два целых числа X и Y называются совместимыми, если результат их побитового «И» равен нулю, то есть X AND Y = 0. Например, числа 77 (10011012) и 50 (1100102) совместимы, так как 10011012 AND 1100102 = 02, а числа 3 (112) и 6 (1102) несовместимы, так как 112 AND 1102 = 102.

Вам дан массив целых чисел A1, A2,..., An. Требуется определить для каждого элемента массива, количество совместимых элементов с ним в данном массиве.

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

В первой строке записано целое число n (1 ≤ n ≤ 105) - количество элементов в данном массиве. Во второй строке через пробел записаны n целых чисел A1, A2, ..., An (1 ≤ Ai ≤ 4 * 106) - элементы данного массива. Числа в массиве могут повторяться.

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

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

Пояснение

В первом примере элемент A1 совместим с элементом A2, поэтому ответ: 1 1.

Во втором примере элемент A1 совместим с элементами A2, A4, элемент A2 совместим с элементами A1, A4, A5, элемент A3 совместим с элементом A4, элемент A4 совместим с элементами A1, A2, A3, элемент A5 совместим с элементом A2, поэтому ответ: 2 3 1 3 1.