Number of Compatible Numbers

Two integers X and Y are considered compatible if their bitwise "AND" operation results in zero, i.e., X AND Y = 0. For instance, the numbers 77 (1001101[2]) and 50 (110010[2]) are compatible because 1001101[2] AND 110010[2] equals 0[2]. Conversely, the numbers 3 (11[2]) and 6 (110[2]) are not compatible since 11[2] AND 110[2] equals 10[2].

You are provided with an array of integers A[1], A[2], ..., A[n]. Your task is to determine, for each element in the array, how many other elements in the array are compatible with it.

Input

The first line contains an integer n (1 ≤ n ≤ 10^5), representing the number of elements in the array. The second line contains n integers A[1], A[2], ..., A[n] (1 ≤ A[i] ≤ 4 * 10^6), which are the elements of the array. The numbers in the array may repeat.

Output

Output n integers separated by spaces, where each integer represents the number of compatible numbers for the corresponding i-th element of the array.

Examples

Note

In the first example, element A[1] is compatible with element A[2], so the output is: 1 1.

In the second example, element A[1] is compatible with elements A[2], A[4]; element A[2] is compatible with elements A[1], A[4], A[5]; element A[3] is compatible with element A[4]; element A[4] is compatible with elements A[1], A[2], A[3]; element A[5] is compatible with element A[2]. Therefore, the output is: 2 3 1 3 1.