ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1059. Expression

Time limit: 1.0 second
Memory limit: 64 MB
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:
  1. If the expression consists of only one operand, then the value of the operand is the value of the expression.
  2. Otherwise:
    • 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
  3. 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

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

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.

Sample

inputoutput
1
0
X
*
1
+
Problem Source: Rybinsk State Avia Academy