Taco's Special Sort

Given an array of non-negative integers, your task is to sort the array based on the following rules:

• First, sort according to the number of 1s in their binary representation, in ascending order. Formally, for an integer \( x \), we denote \( f(x) = \text{number of ones in the binary representation of } x \). The sorting should be primarily based on \( f(x) \).
• If two integers have the same \( f(x) \) value, then sort them by their numerical value in ascending order.

For example, given the list [4, 1, 7, 3, 2]:

• Binary of 4: 100 (1 one)
• Binary of 1: 1 (1 one)
• Binary of 7: 111 (3 ones)
• Binary of 3: 11 (2 ones)
• Binary of 2: 10 (1 one)

After sorting, the output should be: 1 2 4 3 7 because 1, 2, and 4 each have one 1 (sorted in ascending order), followed by 3 (with two 1s) and then 7 (with three 1s).

Note: All input will be provided via standard input (stdin) and the output must be printed to standard output (stdout).

inputFormat

The first line contains a single integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated non-negative integers.

For example:

5
4 1 7 3 2

outputFormat

Print the sorted array as a single line of space-separated integers.

For the above sample, the output should be:

1 2 4 3 7

## sample

5
4 1 7 3 2

1 2 4 3 7