Little Difference

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

Medium6Number theoryMathBrute forceNo attempts yetTime limit3sMemory limit512 MB

Problem

Lidia likes playing with numbers. Today she has a positive integer nn, 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 nn. 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 nn (1n10181 \le n \le 10^{18}).

Output

If the number of decompositions is infinite, print 1-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 kk of that decomposition first, then the kk 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 kk.