Sum of a Geometric Series

Time limit2sMemory limit1024 MB

Summary

Given N up to 10^12, find a geometric series with at least 3 positive integer terms and integer ratio above 1 whose sum is N, or report that none exists.

Level: Medium6 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

A geometric series is a sequence in which the ratio of two consecutive terms is constant.

1, 2, 4, 8, 16, 32...
4, 12, 36, 108, 324...

Among geometric series whose terms are all positive integers, find one whose sum is N, that has at least 3 terms, and whose common ratio is a positive integer greater than 1.

If there are multiple valid answers, output any one of them. If there is no valid answer, output -1.

Input

An integer N, the sum of the geometric series, is given. (1 ≤ N ≤ 10^12)

Output

If a geometric series satisfying the conditions exists, output the number of terms K(K ≥ 3) on the first line. On the second line, output the geometric series in order, separated by spaces.

If no geometric series satisfying the conditions exists, output -1.

Constraints

Every term of the geometric series is a positive integer, and the common ratio is a positive integer greater than 1.

Examples2

Example 1
Input
```
120
```
Expected output
```
4
3 9 27 81
```
Example 2
Input
```
8
```
Expected output
```
-1
```