Anu has created her own function f: f(x,y)=(x|y)?y where | denotes the bitwise OR operation. For example, f(11,6)=(11|6)?6=15?6=9. It can be proved that for any nonnegative numbers x and y value of f(x,y) is also nonnegative.She would like to research more about this function and has created multiple problems for herself. But she isn't able to solve all of them and needs your help. Here is one of these problems.A value of an array [a1,a2,…,an] is defined as f(f(…f(f(a1,a2),a3),…an?1),an) (see notes). You are given an array with not necessarily distinct elements. How should you reorder its elements so that the value of the array is maximal possible?

Input

The first line contains a single integer n (1≤n≤105).The second line contains n integers a1,a2,…,an (0≤ai≤109). Elements of the array are not guaranteed to be different.Output Output n integers, the reordering of the array with maximum value. If there are multiple answers, print any.

Examples
inputCopy

4 4 0 11 6

outputCopy

11 6 4 0

inputCopy

1 13

outputCopy

13

Note

In the first testcase, value of the array [11,6,4,0] is f(f(f(11,6),4),0)=f(f(9,4),0)=f(9,0)=9. [11,4,0,6] is also a valid answer.

我們把a(bǔ)|b-b換成 a-a&b，也就是說(shuō)使得a&b最小，那我們考慮什么時(shí)候最大，即所有數(shù)的最高位，只有一個(gè)為1不然一定在運(yùn)算的過(guò)程中被削去，那么這個(gè)題就可以改成，在32位中找某一位只有一個(gè)數(shù)是1的那一個(gè)數(shù)，讓他當(dāng)?shù)谝?。因?yàn)槠溆喽紩?huì)抵消。如果不存在，那么怎樣輸出都是0

#include <bits/stdc++.h> using namespace std; const int N = 100003; int n, a[N]; int main() {cin >> n;for (int i = 1; i <= n; ++i){cin >> a[i];}for (int j = 30; ~j; --j){int cnt = 0, p;for (int i = 1; i <= n; ++i)if ((a[i] >> j) & 1)++cnt, p = i;if (cnt == 1){printf("%d ", a[p]);for (int k = 1; k <= n; ++k)if (k != p)printf("%d ", a[k]);return 0;}}cout<<endl<<endl;for (int i = 1; i <= n; ++i)printf("%d ", a[i]); }

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #618 (Div. 2)-C. Anu Has a Function的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。