Decomposing Integers with Nearly Equal Factors

Little Lidia loves playing with numbers. Today she is given a positive integer \(n\) and she wants to decompose it into a product of positive integers. However, because she likes numbers that are close to each other, in every valid decomposition the factors must differ by at most one.

More formally, a decomposition of \(n\) is a multiset \(\{a_1,a_2,\dots,a_k\}\) of positive integers such that

[ a_1\times a_2\times\cdots\times a_k = n, ]

and for any two factors \(a_i\) and \(a_j\) it holds that \(|a_i-a_j|\le 1\). Two decompositions are considered the same if they have the same number of factors and one can be transformed into the other by a permutation.

Your task is to list all possible decompositions satisfying these conditions. In each decomposition, output the factors in non-decreasing order. The decompositions should be ordered primarily by the number of factors (increasing), and for decompositions with the same number of factors, in lexicographical order.

inputFormat

The input consists of a single line containing a positive integer \(n\) (\(1\le n\le 10^{12}\)).

outputFormat

For each valid decomposition, output one line containing the factors (in non-decreasing order) separated by a single space.

If there is no valid decomposition, output nothing. (Note: Since \(n\) itself is always a valid decomposition, there will be at least one output.)

sample

12

12
3 4
2 2 3