题目描述

在一个大型企业的设备管理系统中，每个智能设备的工作状态由一个整数表示，这个整数的二进制形式的每一位代表设备的不同功能开关的状态。为了系统的便捷管理和高效操作，需要将这些设备按照它们的工作状态（即二进制表示中 1 的个数）进行排序，开启的功能越少的设备，需要排在前面。排序规则如下：

1. 首先，按照二进制表示中 1 的个数从少到多排序。
2. 若两个设备的工作状态有相同数量的 1，则按设备状态的数值从小到大排序。

请你实现一个算法，完成这种排序。

例如，对于下面的三台设备的工作状态：

4 3 7

他们的二进制表示为：

100 011 111

第一台设备的第一个功能是启动的。

第二台设备的后两个功能是启动的。

第三台设备的全部三个功能都是启动的。

因此，按照排序规则，需要把4$(二进制: 100)$放在前面，3排第二，7由于全部的功能都启动了，所以7排在最后。

输入格式

第一行包含一个整数 $n$，表示数组 a 的长度。 第二行包含 $n$ 个整数，表示数组 a 的元素，代表多个设备的工作状态。

输出格式

输出一行，包含 $n$ 个整数，表示排序后的设备工作状态。

样例数据

3
4 3 7

4 3 7

5
0 1 2 3 4

0 1 2 4 3

4
1023 512 256 768

256 512 768 1023

样例解释

在第一个样例中，数字 4、1、7 的二进制分别为 100、001、111。1 的个数分别为 1、1、3。按照规则，先排序 1 和 4（1 个 1），按照数字大小从小到大排列，然后是 7。因此排序后为 1 4 7。

在第二个样例中，数字 0、1、2、3、4 的二进制分别为 0、1、10、11、100，1 的个数分别为 0、1、1、2、1。按照规则，先是 0（0 个 1），然后是 1、2、4（各有 1 个 1，按数字大小排序），最后是 3（2 个 1）。因此排序后为 0 1 2 4 3。

数据范围

• $1 \leq n \leq 10^5$
• $0 \leq a[i] \leq 10^9$