Капсулы для жирафов

В «Жираф-Отеле» места продаются не поштучно, а капсулами. Капсула на 1 место, на 2 места, на 4 места, на 8 мест и так далее — всегда степень двойки.

Администратор разрешает заказать несколько капсул, но каждую капсулу надо брать целиком. Нужно разместить ровно N жирафов.

Ты хочешь заказать минимально возможное число капсул.

Выведи, какие вместимости капсул надо взять. Если решений несколько, выбери то, где список вместимостей отсортирован по возрастанию (это делает ответ однозначным).

Формат ввода

В первой строке дано целое число t — количество наборов данных.

Далее идут t наборов данных. В каждом наборе дано одно целое число N.

Формат вывода

Для каждого набора данных выведите ответ.

В первой строке ответа на каждый набор выведите k — сколько капсул нужно заказать. Во второй строке ответа на каждый набор выведите k целых чисел — вместимости капсул (степени двойки) в возрастающем порядке.

Ограничения

• 1 ≤ t ≤ 4
• 1 ≤ N ≤ 1 000 000 000
• Сумма значений N по всем наборам не превышает 1 000 000 000
• Каждая вместимость должна быть степенью двойки: 1, 2, 4, 8, ...
• Сумма выведенных вместимостей должна быть ровно N
• k должно быть минимально возможным

Пример

Ввод 3 1 2 3

Вывод 1 1 1 2 2 1 2

Ключевое наблюдение: любые капсулы — это степени двойки, а число N единственным образом представляется как сумма некоторых разных степеней двойки (это просто его двоичная запись). Там, где в двоичном виде стоит бит 1, мы берём капсулу соответствующей вместимости. Такое разложение автоматически даёт минимальное число капсул: заменить одну капсулу 2^t можно только несколькими меньшими (например 2^t = 2^(t-1)+2^(t-1)), а это увеличит количество.

Почему приём работает: мы выбираем ровно те степени двойки, которые «включены» в N. Число выбранных капсул равно числу единиц в двоичной записи (popcount), и меньше уже нельзя.

План:

• Заведи список parts.
• Пока N > 0:
• Найди наименьшую степень двойки, которая входит в N (самый младший установленный бит): lowbit = N & -N.
• Добавь lowbit в список.
• Вычти её из N.
• Выведи k = len(parts) и элементы parts.

Фишка: при вычитании lowbit биты убираются снизу вверх, поэтому parts уже получаются в возрастающем порядке.

Сложность: O(кол-ва установленных битов) (не больше ~30 для N ≤ 1e9).

Частая ошибка: собирать степени двойки перебором битов сверху вниз и забыть отсортировать — по условию нужен возрастающий список.