In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 2nd
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #04 exercise sheet]

[AED013] Counting the Bits

Count von Count has just found out that he can compute the number of 1 bits in a number! He needs your help to sort a set of numbers based on this.

The Problem

Given N distinct integers, your task is to sort them in 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 contains an integer N: the amount of numbers to consider.

The second line contains N distinct integers X₁ X₂ ... X_N, the numbers you want to sort.

Output

The output should consist of N lines, containing the numbers sorted in the indicated order (one number per line).

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

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)