Problem D
Primal Representation

The fundamental theorem of arithmetic says that every integer can be represented as a unique product of prime numbers. For example, consider the number $319\, 176$. It can be written as the product $31 \times 3 \times 3 \times 2 \times 2 \times 2 \times 13 \times 11$, or more succinctly as $31 \times 3^2 \times 2^3 \times 13 \times 11$ if we collect the common factors. And, of course we could rearrange these product terms in any order.

Write a program that reads integers as input, and for each integer print out the representation of that integer as a product of primes and their exponents.

Input

Input is a list of at most $10\, 000$ integers, one per line, ending at end of file. Each integer $x$ has the property that $2 \leq |x| \leq 2^{31}-1$.

Output

For each input integer $x$, print a line with a prime factorization of $x$. Combine common factors using exponential notation, and order the factors by the value of the base (from least to greatest). Separate factors using spaces, but don’t use spaces between a base and its exponent. If $x$ is negative, prepend “-1 ” to the factorization of $|x|$.

2
3
4
10
11
12
13
20
21
22
23
24
30
-30

2
3
2^2
2 5
11
2^2 3
13
2^2 5
3 7
2 11
23
2^3 3
2 3 5
-1 2 3 5