[PC006] Special Sort

You are given an array of \(n\) distinct integers. Your task is to sort the array into descending order according to the number of 1's in their binary representation. If two numbers have the same number of 1's, you have to sort them in ascending order of their value.

Input

The first input line an integer \(n\): the amount of numbers in the array.

The second line contains \(n\) integers \(x_1, x_2, \ldots, x_n\): the numbers of the array sorted as described above.

Output

A single line containing the numbers in sorted order, separated by single spaces (there should be no space after the last number).

Constraints

• \( 1 \leq n \leq 10^5 \)
• \( 1 \leq x_i \leq 10^9 \)

8
5 2 15 3 9 4 6 7

15 7 3 5 6 9 2 4

The binary representation of each number in the input is:

• 15: 1111 (four 1's)
• 7: 0111 (three 1's)
• 3: 0011 (two 1's)
• 5: 0101 (two 1's)
• 6: 0110 (two 1's)
• 9: 1001 (two 1's)
• 2: 0010 (one 1)
• 4: 0100 (one 1)