Internet Problem Solving Contest

• Easy input data set – E1
• Hard input data set – E2

Little Michael got a really interesting present last Christmas. It was a box full of colorful tiles with fancy symbols. After a closer inspection, Michael found out that there were several types of tiles. There were red tiles displaying symbols "+", "*", "!", green tiles with symbols "(" and ")", and a few blue tiles with large symbols "1" across their faces.

Michael soon realized that red tiles represented mathematical operations: + stood for addition, * for multiplication, ! for the factorial function. (The factorial of a positive integer n is defined as the product of all positive integers less than or equal to n, i.e. n! = n(n-1)(n-2)...2.1.) Green tiles certainly represented left and right parentheses. But why were there only a few blue tiles and each of them had a 1 on its top?

The brochure he found in the box after taking all the tiles out said that the game was named "Express your number". It claimed that the game is a great companion for his free time and is good for players of all skills and ages. It went further explaining that the point of the game is to find an expression consisting of additions, multiplications, factorials, parentheses and numbers 1 that would evaluate to a given number n. The brochure also contained a list of sample numbers and encouraged him to find expressions for them. Michael soon realized that since there were only a few blue tiles, he had to find expressions that would not contain too many 1s. Now he is trying to express every number by an expression that contains as few 1s as possible.

Formally,

1. 1 is an expression.
2. If e is an expression then (e) and e! are expressions.
3. If e₁ and e₂ are expressions then e₁+e₂ and e₁*e₂ are expressions.
4. Nothing else is considered to be an expression.

Expressions are evaluated using standard precedence rules (i.e. ! has the highest priority, followed by * with a lower priority and + with the lowest priority). Note that it is not possible to obtain a number by concatenating digits, i.e. 11 is not a valid expression.

Input file specification

The input file contains a list of positive integers, one per line. The list is terminated by the number -1, which should not be processed.

Output file specification

Express each number in the input file by an expression that contains the minimum number of 1s. If there are multiple such expressions, output an arbitrary one of them. For technical reasons, we allow only expressions that consist of no more than 10000 symbols. Output an empty line after each expression. You can delimit characters in your expression by spaces and divide your expression into multiple lines. Do not insert any blank lines inside expressions!

Example

Input file:

18
5040
11
-1

Output file: (out of several possibilities)

(1+1+1)*(1+1+1)!

((1+1+1)!+1)!

((1+1+1+1)+1)*(1+1)+1