Кількість сумісних чисел

Два цілі числа 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-го елемента масиву.

Приклади

Примітка

У першому прикладі елемент 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.