Cardinality Sorting

Sort first by the number of 1s in the binary representation in ascending order, then by integer value in ascending order for equal counts; all duplicate elements are kept.

输入格式

The first line contains n, and the second line contains n integers. Full original bounds: 1≤n≤100000, 1≤a[i]≤1000000.

输出格式

Output the n sorted integers, separated by spaces.

样例 1

输入：

5
31 15 7 3 2

输出：

2 3 7 15 31

样例 2

输入：

5
1 2 3 4 5

输出：

1 2 4 3 5

样例 3

输入：

3
3 3 1

输出：

1 3 3

样例说明

The outputs of the three public examples are, in order: 2 3 7 15 31; 1 2 4 3 5; 1 3 3. They were verified by independent enumeration or direct simulation.