Problems
Калькулятор
Калькулятор
Имеется калькулятор, который выполняет следующие операции:
умножить число X на 2;
умножить число X на 3;
прибавить к числу X единицу.
Определите, какое наименьшее количество операций требуется, чтобы получить из числа 1 число N.
Input data
Во входном файле написано натуральное число N, не превосходящее 10^6.
Output data
В первой строке выходного файла выведите минимальное количество операций. Во второй строке выведите числа, последовательно получающиеся при выполнении операций. Первое из них должно быть равно 1, а последнее N. Если решений несколько, выведите любое.
Examples
Input example #1
1
Output example #1
0 1