Юный гений Гриша сконструировал ракету. Чтобы она взлетела, нужна мощность N условных энергетических единиц, для этого Гриша планирует задействовать отделяемые части - ступени. У Гриши остались ступени только мощностью по 1, 5 и 8 энергетических единиц, каждой ступени - неограниченное количество. Весят все ступени одинаково, но общее количество ступеней нужно минимизировать. Помогите Грише определить
- какое минимальное количество ступеней надо, чтобы набрать нужную суммарную мощность;
- выведите список всех ступеней в порядке неубывания их мощностей; если набор ступеней может быть различным, выведите любой подходящий (при условии минимизации общего числа ступеней)
- определите ступеней какой мощности будет больше всего выдано.
Входные данные
В первой строке записана требуемая сумма n (1 <= n <= 100000).
Выходные данные
Выведите в первой строке наименьшее возможное количество ступеней.
Во второй строке выведите через пробел список мощностей всех используемых ступеней, в порядке возрастания их мощности.
В третьей строке выведите одно число - мощность ступени, количество которых было больше всего задействовано. Eсли таких мощностей несколько, выведите наименьшее значение
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
1
1
1
|
|
2
|
16
|
2
8 8
8
|