Little Difference

Time limit3sMemory limit512 MB

Summary

List all factorizations of n into factors that differ by at most 1, or report infinitely many.

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

Problem

Lidia likes playing with numbers. Today she has a positive integer $n$ , and she wants to write it as a product of positive integers.

Lidia likes numbers that sit close together, so any two numbers used in a decomposition differ by at most 1, and the product of all numbers in the decomposition must equal $n$ . Two decompositions are the same when they have the same number of elements and one is a permutation of the other.

Write a program that finds every decomposition Lidia can play with today.

Input

The only line contains one integer $n$ ( $1 \le n \le 10^{18}$ ).

Output

If the number of decompositions is infinite, print $-1$ on the first line and nothing else.

Otherwise print the number of decompositions on the first line. Then print one decomposition per line. On each line print the number of elements $k$ of that decomposition first, then the $k$ elements in non-decreasing order, separated by single spaces.

Two different decompositions always have a different number of elements, so print the lines in increasing order of $k$ .

Examples3

Example 1
Input
```
12
```
Expected output
```
3
1 12
2 3 4
3 2 2 3
```
Example 2
Input
```
1
```
Expected output
```
-1
```
Example 3
Input
```
36
```
Expected output
```
4
1 36
2 6 6
3 3 3 4
4 2 2 3 3
```