Compatible Numbers

4000ms

262144K

Description:

Two integers x and y are compatible, if the result of their bitwise "AND" equals zero, that is, a & b = 0. For example, numbers 90 (1011010₂) and 36 (100100₂) are compatible, as 1011010₂ & 100100₂ = 0₂, and numbers 3 (11₂) and 6 (110₂) are not compatible, as 11₂ & 110₂ = 10₂.

You are given an array of integers a₁, a₂, ..., a_n. Your task is to find the following for each array element: is this element compatible with some other element from the given array? If the answer to this question is positive, then you also should find any suitable element.

Input:

The first line contains an integer n (1 ≤ n ≤ 10⁶) — the number of elements in the given array. The second line contains n space-separated integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 4·10⁶) — the elements of the given array. The numbers in the array can coincide.

Output:

Print n integers ans_i. If a_i isn't compatible with any other element of the given array a₁, a₂, ..., a_n, then ans_i should be equal to -1. Otherwise ans_i is any such number, that a_i & ans_i = 0, and also ans_i occurs in the array a₁, a₂, ..., a_n.

Sample Input:

2
90 36

Sample Output:

36 90

Sample Input:

4
3 6 3 6

Sample Output:

-1 -1 -1 -1

Sample Input:

5
10 6 9 8 2

Sample Output:

-1 8 2 2 8

Informação

Provedor Codeforces

Código CF165E