Petr got an assignment to cipher out the value of polynomial P with calculator working in mode of reverse polish record. His calculator is able only to add and multiply numbers of any length (capacity). Input data — degree of the polynomial, argument x and coefficient values.
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. Reference notes. Expression written in mode of reverse polish record consists of operands and signs of operations; the sign of operation is preceded by operands. The brackets in reverse polish record 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 operand is the value of the expression.
- seek for the first operation sign leftmost in the expression
- process the operation with those operands that stand to the left from this sign
- write the result instead of the sign and operands
- recalculate the ultimate expression using rules 1-2
- If rules 1-2 are unacceptable, then the expression hasn’t been properly written.
Example. Expression of reverse polish record “a b c d + * e - /” is the equivalence of ordinary expression “a / (b * (c + d) – e)”
Input contains an integer N (1 ≤ N ≤ 1000). Here you assume that polynom is a0xN+
a1xN−1 + … .
Instead of the coefficient ai you may just write the number i.
Output should contain a sequence of minimal length corresponding to polynomial in reverse polish record. This record can include only signs of operations ('+', '*'), capital Latin letter X and unsigned integers that set the weights of coefficients of x degrees.
Each element (sign of operation, symbol X, weight of coefficient) should be written without initial space characters by one in a line.
Problem Source: Rybinsk State Avia Academy