Make It One 2

Interview

Time limit0.5sMemory limit512 MB

Summary

Find the fewest operations (divide by 3, divide by 2, or subtract 1) turning N into 1, and print the lexicographically smallest shortest path.

Level: Medium5 of 10
Topics: Dynamic programming, BFS, Greedy
Solved: No attempts yet

Problem

The operations you can use on an integer X are these three.

If X is divisible by 3, divide it by 3.
If X is divisible by 2, divide it by 2.
Subtract 1.

Given an integer N, you want to reach 1 by applying those three operations. Find the minimum number of operations, together with the numbers you pass through while achieving that minimum.

Input

The first line contains a natural number N with $1 \le N \le 10^6$ .

Output

On the first line, print the minimum number of operations.

On the second line, print the numbers you pass through while turning N into 1, separated by single spaces and in order. The first number is N and the last number is 1.

If several sequences achieve the minimum, print only the lexicographically smallest one. Every sequence that achieves the minimum has the same length, so compare two sequences from the front: the one with the smaller number at the first position where they differ comes first.

Examples2

Example 1
Input
```
2
```
Expected output
```
1
2 1
```
Example 2
Input
```
10
```
Expected output
```
3
10 9 3 1
```