Petr got an assignment to calculate the value of polynomial P of degree N by its coefficient values and argument x.
Petr has a calculator working in a mode of reverse Polish notation. His calculator is able to add and multiply numbers of any length (capacity).
Help Petr to set correct and at the same time the shortest sequence of operands and signs of operations in the order of entering in calculator.
Expression written in a mode of reverse Polish notation consists of operands and signs of operations; the sign of operation is preceded by operands. The brackets in reverse Polish notation are eliminated. The algorithm to compute such an expression is the following:
- If the expression consists of only one operand, then the value of the expression is the value of this operand.
- seek for the first operation sign leftmost in the expression
- process the operation with those two operands that stand to the left from this sign
- write the result of this operation instead of the sign and the operands
- repeat the steps 1-2
- If the rules 1-2 are unacceptable, then the initial expression was incorrect.
For example, the reverse Polish notation “a b c d + * e + /” is the equivalence of ordinary expression “a / (b * (c + d) + e)”.
The only line contains an integer N (1 ≤ N ≤ 1000).
Output a sequence of minimal length corresponding to polynomial of degree N in reverse Polish notation.
The polynomial has a form a0xN+a1xN−1 + … aN.
This sequence can include only signs of operations “+” and “*”, capital Latin letter “X” and non-negative integers that correspond the coefficients numbers (the integer i denotes the coefficient ai).
All elements (signs of operations, characters “X” and numbers of coefficients) should be written by one in a line.
Problem Source: Rybinsk State Avia Academy