Digit Short Coding

Time limit1sMemory limit1024 MB

Summary

Given N up to 10^8, find the shortest postfix expression of digits, * and ^ that evaluates to N.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Number theory
Solved: No attempts yet

Problem

A positive integer $N$ is given. Find the shortest expression that represents $N$ using the digits 0 through 9 and the operators multiplication * and exponentiation ^.

Write the expression in postfix notation, and separate each number or operator with a space. Spaces do not count toward the length of the expression.

Input

A positive integer $N$ is given. $(1 \leq N \leq 10^8)$

Output

Print the shortest expression representing $N$ in postfix notation. If several shortest expressions exist, print any one of them.

Hint

Postfix notation writes each operator after its operands. Reading the expression from left to right, push numbers onto a stack. When an operator appears, pop two numbers from the stack, compute the result, and push it back.

For example, the postfix expression 3 2 3 * ^ evaluates to $729$ as follows.

$3$ , $2$ , and $3$ are pushed onto the stack in order.
Pop $2$ and $3$ , compute their product $2\times 3 = 6$ , and push it onto the stack.
Pop $3$ and $6$ , compute the power $3^6=729$ , and push it onto the stack.

Examples2

Example 1
Input
```
1
```
Expected output
```
1
```
Example 2
Input
```
10000
```
Expected output
```
10 4 ^
```