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

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

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

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

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

Формат ввода

Одно целое число N.

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

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

Ограничения

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

Пример

Ввод 13

Вывод 3 1 4 8

Ключевое наблюдение: любые капсулы — это степени двойки, а число 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).

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