eolymp
bolt
Try our new interface for solving problems
Problems

Калькулятор

Калькулятор

Time limit 1 second
Memory limit 64 MiB

Имеется калькулятор, который выполняет следующие операции:

  • умножить число 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