#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class c, class b>
  debug& operator<<(pair<b, c> d) {
    return *this << "(" << d.first << ", " << d.second << ")";
  }
  template <class c>
  debug& operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
};
long double eps = (long double)1 / 1e6;
const long double pi = 3.14159265359;
int inf = 1e9, mod1 = 1e9 + 7;
long long sqr(long long a) { return a * a; }
long long qb(long long a) { return a * a * a; }
template <typename T>
bool umax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umin(T& a, T b) {
  return b < a ? a = b, 1 : 0;
}
bool is_prime(long long val) {
  for (long long i = 2; i <= sqrt(val); i++)
    if (val % i == 0) return 0;
  return 1;
}
long long gcd(long long a, long long b) { return !a ? b : gcd(b % a, a); }
long long binpow(long long a, long long b, long long mod) {
  return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod
                    : sqr(binpow(a, b / 2, mod)) % mod)
           : 1;
}
long long binmult(long long a, long long b, long long mod) {
  return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod
                    : (2 * binmult(a, b / 2, mod)) % mod)
           : 0;
}
const long long RR = 1e4;
const long long tx[8] = {1, -1, 2, -2, -1, -2};
const long long ty[8] = {-2, -2, -1, -1, 2, 1};
const char rev_to[4] = {'E', 'W', 'N', 'S'};
const int block = 600;
const int OPEN = 0;
const int CLOSE = 1;
const int STOP = 2;
auto rnd = bind(uniform_int_distribution<long long>(1, 10), mt19937(time(0)));
void bad() {
  cout << "-1";
  exit(0);
}
const int N = 4e6 + 1;
const int lg = 22;
int dp1[1 << lg];
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  ;
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& z : a) cin >> z;
  int x = (1 << lg) - 1;
  for (int i = 0; i < n; i++) {
    umax(dp1[x ^ a[i]], i + 1);
  }
  for (int mask = x; mask >= 0; mask--) {
    for (int j = 0; j < lg; j++) {
      if ((1ll << j) & mask) {
        umax(dp1[mask ^ (1ll << j)], dp1[mask]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    int first = dp1[a[i - 1]];
    if (first == 0) {
      cout << -1 << ' ';
    } else
      cout << a[first - 1] << ' ';
  }
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 (10110102) and 36 (1001002) are compatible, as 10110102 & 1001002 = 02, and numbers 3 (112) and 6 (1102) are not compatible, as 112 & 1102 = 102.

You are given an array of integers a1, a2, ..., an. 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 ≤ 106) — the number of elements in the given array. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 4·106) — the elements of the given array. The numbers in the array can coincide.

Output

Print n integers ansi. If ai isn't compatible with any other element of the given array a1, a2, ..., an, then ansi should be equal to -1. Otherwise ansi is any such number, that ai & ansi = 0, and also ansi occurs in the array a1, a2, ..., an.

Examples

Input

2
90 36


Output

36 90

Input

4
3 6 3 6


Output

-1 -1 -1 -1

Input

5
10 6 9 8 2


Output

-1 8 2 2 8

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  ~debug() { cerr << endl; }
  template <class c>
  typename enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) {
    cerr << boolalpha << i;
    return *this;
  }
  template <class c>
  typename enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) {
    return *this << range(begin(i), end(i));
  }
  template <class c, class b>
  debug& operator<<(pair<b, c> d) {
    return *this << "(" << d.first << ", " << d.second << ")";
  }
  template <class c>
  debug& operator<<(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it;
    return *this << "]";
  }
};
long double eps = (long double)1 / 1e6;
const long double pi = 3.14159265359;
int inf = 1e9, mod1 = 1e9 + 7;
long long sqr(long long a) { return a * a; }
long long qb(long long a) { return a * a * a; }
template <typename T>
bool umax(T& a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umin(T& a, T b) {
  return b < a ? a = b, 1 : 0;
}
bool is_prime(long long val) {
  for (long long i = 2; i <= sqrt(val); i++)
    if (val % i == 0) return 0;
  return 1;
}
long long gcd(long long a, long long b) { return !a ? b : gcd(b % a, a); }
long long binpow(long long a, long long b, long long mod) {
  return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod
                    : sqr(binpow(a, b / 2, mod)) % mod)
           : 1;
}
long long binmult(long long a, long long b, long long mod) {
  return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod
                    : (2 * binmult(a, b / 2, mod)) % mod)
           : 0;
}
const long long RR = 1e4;
const long long tx[8] = {1, -1, 2, -2, -1, -2};
const long long ty[8] = {-2, -2, -1, -1, 2, 1};
const char rev_to[4] = {'E', 'W', 'N', 'S'};
const int block = 600;
const int OPEN = 0;
const int CLOSE = 1;
const int STOP = 2;
auto rnd = bind(uniform_int_distribution<long long>(1, 10), mt19937(time(0)));
void bad() {
  cout << "-1";
  exit(0);
}
const int N = 4e6 + 1;
const int lg = 22;
int dp1[1 << lg];
signed main() {
  cin.tie(0);
  cout.tie(0);
  ios_base::sync_with_stdio(0);
  ;
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& z : a) cin >> z;
  int x = (1 << lg) - 1;
  for (int i = 0; i < n; i++) {
    umax(dp1[x ^ a[i]], i + 1);
  }
  for (int mask = x; mask >= 0; mask--) {
    for (int j = 0; j < lg; j++) {
      if ((1ll << j) & mask) {
        umax(dp1[mask ^ (1ll << j)], dp1[mask]);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    int first = dp1[a[i - 1]];
    if (first == 0) {
      cout << -1 << ' ';
    } else
      cout << a[first - 1] << ' ';
  }
  return 0;
}

```