# 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|$.

Sample Input 1 | Sample Output 1 |
---|---|

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 |