You are given ** N** positive integers.

For every integer, you can choose to either swap two bits in its binary representation, or do nothing.

Your task is to compute the maximum integer that can be obtained from every given value.

### Input

The first line of input contains ** N**.

The second line of input contains

**space-separated integers.**

`N`### Output

The only line of output should contain all ** N** maximum values that can be obtained, separated by spaces.

### Restrictions

`1 ≤ N ≤ 1000``0 ≤ any number < 2`^{31}

### Sample

Input | Output |
---|---|

41 5 6 9 | 1 6 6 12 |

## Approach #1

Try to swap each pair of bits once, and choose the maximum value. Complexity: `O(log ^{2} N)`

## Approach #2

The maximum value can be obtained by swapping the first occurrence of a ** 0** bit with the last occurrence of a

**bit. Complexity:**

`1`**.**

`O(log N)`Haskell implementation:

import Numeric (showIntAtBase, readInt) import Data.Char (intToDigit, digitToInt) import Data.List bin x = showIntAtBase 2 intToDigit x "" dec s = foldl' (\acc x -> acc * 2 + digitToInt x) 0 s best x | not (elem '0' x) = x | not (elem '1' x) = x | firstZero > lastOne = x | otherwise = front ++ "1" ++ middle ++ "0" ++ back where front = take firstZero x middle = take (lastOne-firstZero-1) (drop (firstZero+1) x) back = drop (lastOne+1) x firstZero = head $ elemIndices '0' x lastOne = last $ elemIndices '1' x main = do input <- getContents let xs = map read $ words $ last $ lines input :: [Int] putStrLn $ concat $ intersperse " " $ map (show . dec . best . bin) xs