26716번 - Muzyka pop 2 다국어

문제

Jak być może pamiętacie, Mateusz uwielbia muzykę pop. Właśnie skomponował nowy utwór i pozostaje mu tylko ułożyć do niego odpowiednie zakończenie.

Mateusz chce, aby zakończenie jego utworu składało się z pewnego niepustego ciągu nut, gdzie każdą można opisać przez jej głośność, która to jest dodatnią liczbą całkowitą. Mateusz może używać nut o dowolnie dużych głośnościach, jednak zadaniem zakończenia jest stopniowe wygaszenie utworu – z tego względu głośności nut w zakończeniu muszą tworzyć ciąg ściśle malejący.

Jak pewnie wiecie lub pamiętacie, w muzyce pop ważne są dobre bity. Tym razem Mateusz stwierdził, że nuta o głośności x ma moc bitową równą liczbie zapalonych bitów w binarnym zapisie liczby x. Biorąc pod uwagę resztę utworu ustalił, że suma mocy bitowych nut w zakończeniu powinna być równa dokładnie n.

Pomóż mu i znajdź odpowiedni ciąg głośności nut. Można udowodnić, że zawsze istnieje co najmniej jeden taki ciąg, więc Twoim zadaniem jest znaleźć minimalny leksykograficznie.

Uwaga: Mówimy, że ciąg liczbowy A jest mniejszy leksykograficznie od ciągu liczbowego B, jeśli na pierwszej pozycji, na której te ciągi się różnią, A zawiera liczbę mniejszą od B. Jeśli taka pozycja nie istnieje, to A jest mniejszy leksykograficznie od B, jeśli A jest krótszy od B. Na przykład ciąg [1, 10000000] jest mniejszy leksykograficznie od ciągu [2, 2], ciąg [4, 2, 20, 30, 40] jest mniejszy leksykograficznie od ciągu [4, 2, 100, 1], a ciąg [5, 4, 3, 2] jest mniejszy leksykograficznie od ciągu [5, 4, 3, 2, 1].

입력

W jedynym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 1 000 000), oznaczająca wymaganą sumę mocy bitowych nut w szukanym ciągu.

출력

W pierwszym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita k, oznaczająca długość szukanego ciągu.

W drugim wierszu standardowego wyjścia powinno znaleźć się k dodatnich liczb całkowitych – minimalny leksykograficznie, ściśle malejący ciąg, którego elementy mają sumarycznie zapalonych dokładnie n bitów w zapisie binarnym.

제한

힌트

Wyjaśnienie przykładów: W pierwszym teście przykładowym innymi poprawnymi ciągami są np. [3, 2], [7] lub [4, 2, 1], jednak ciąg [3, 1] jest możliwie najmniejszy leksykograficznie. Zwróć uwagę, że np. ciągi [1, 3], [3, 1, 0] ani [2, 2, 2] nie są poprawnymi ciągami, ponieważ nie są ściśle malejące albo zawierają niedodatnie elementy.