В архиве исследовательского центра хранятся цифровые бейджи сотрудников. Каждый бейдж имеет целый номер.

Для внутренней системы безопасности важен не только сам номер, но и количество включённых битов в его двоичной записи. Чем меньше включённых битов, тем «проще» сигнал бейджа для обработки.

Вам нужно упорядочить номера бейджей по следующим правилам:

• сначала по количеству единиц в двоичной записи числа;
• если количества единиц равны, то по возрастанию самого числа.

Входные данные

В первой строке записано одно целое число n — количество бейджей.

Во второй строке записаны n целых неотрицательных чисел a1, a2, ..., an — номера бейджей.

Выходные данные

Выведите все номера бейджей в порядке, указанном в условии.

Пример 1

Входные данные

9
0 1 2 3 4 5 6 7 8

Выходные данные

0 1 2 4 8 3 5 6 7

Пример 2

Входные данные

6
10 100 3 7 8 9

Выходные данные

8 3 9 10 7 100

Ограничения

• 1 <= n <= 10^5
• 0 <= ai <= 10^9