В конце учебного года декан каждого факультета Хогвартса должен разместить итоговую сумму очков, набранных студентами своего факультета, на специальном магическом табло в Большом зале. Изначально сумма очков на табло для каждого факультета равна нулю. Для того, чтобы выставить на табло нужную сумму, деканы могут использовать лишь три заклинания:
1) «engorgio 1» (увеличивает сумму на табло на 1);
2) «engorgio 5» (увеличивает сумму на табло на 5);
3) «engorgio \(\times2\)» (увеличивает сумму на табло в 2 раза).
Профессор МакГонагалл знает, что она должна установить для факультета Гриффиндор на табло сумму очков, равную \(n\).
Какова длина кратчайшей последовательности применения заклинаний «engorgio», с помощью которых профессор сможет добиться желаемого результата на табло? Приведите пример такой последовательности, обозначая заклинания их номерами.
Формат входных данных
На ввод программе подаётся единственное целое неотрицательное число \(n\). Гарантируется, что \(0\leqslant n\leqslant 10^5\).
Формат выходных данных
Программа должна вывести в первой строке единственное целое неотрицательное число — наименьшую возможную длину последовательности применения заклинаний «engorgio», позволяющей установить на табло число \(n\) при начальном значении 0.
Затем во второй строке программа должна вывести через пробел элементы последовательности номеров заклинаний, позволяющей профессору МакГонагалл установить требуемое значение на табло.
| № | Входные данные | Выходные данные |
|
1
|
0
|
0
|
|
2
|
2
|
2
1 3
|
|
3
|
5
|
1
2
|
|
4
|
2053
|
12
2 2 2 1 3 3 3 3 3 3 3 2
|