D. Derivative of polynomial
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: This problem is rendered better in HTML than in PDF form.

As the problem title suggests, you have to write a program to find the derivative of a polynomial, a polynomial is a string of characters that matches the following recursive definition:

  • A $$$polynomial$$$ is any of:
    • "$$$ 0 $$$"
    • "$$$ {term} $$$"
    • "$$$ -{term} $$$"
    • "$$$ {polynomial}+{term} $$$"
    • "$$$ {polynomial}-{term} $$$"
  • A $$$term$$$ is any of:
    • "$$$ {positiveInt} $$$"
    • "$$$coefficient$$$ $$$x$$$ $$$exponent$$$"
  • A $$$coefficient$$$ is any of:
    • "$$$ {nonOnePositiveInt} $$$"
    • "" (empty string)
  • An $$$exponent$$$ is any of
    • "$$$ \, \widehat{\,}$$$ $$${nonOnePositiveInt} $$$"
    • "$$$ \, \widehat{\,}$$$ $$$- {positiveInt} $$$"
    • "" (empty string)
  • A $$$nonOnePositiveInt$$$ is an integer number greater $$$1$$$, with no leading zeroes.
  • A $$$positiveInt$$$ is an integer number greater than $$$0$$$, with no leading zeroes.

The following are valid $$$nonOnePositiveInt$$$ strings: "$$$2$$$", "$$$10$$$", "$$$94$$$" and "$$$100$$$". But these are invalid $$$nonOnePositiveInt$$$ strings: "$$$-3$$$", "$$$+32$$$", "$$$0$$$" and "$$$1$$$".

The following are valid $$$positiveInt$$$ strings: "$$$1$$$", "$$$10$$$", "$$$94$$$" and "$$$100$$$". But these are invalid $$$positiveInt$$$ strings: "$$$-1$$$", "$$$3.14$$$", "$$$0$$$" and "$$$+32$$$".

The following are valid $$$coefficient$$$ strings: "", "$$$3$$$" and "$$$10$$$". But these are invalid $$$coefficient$$$ strings: "$$$-10$$$", "$$$1$$$" and "$$$0$$$".

The following are valid $$$exponent$$$ strings: "", "$$$\, \widehat{\,} 3$$$" and "$$$\, \widehat{\,} -10 $$$". But these are invalid $$$exponent$$$ strings: "$$$ \, \widehat{\,} 1$$$", "$$$\, \widehat{\,} +30 $$$" and "$$$ \, \widehat{\,} 0$$$".

The following are valid $$$term$$$ strings: "$$$x$$$", "$$$x\,\widehat{\,}3$$$", "$$$4x\,\widehat{\,}-2$$$" and "$$$123$$$". But these are invalid $$$term$$$ strings: "$$$0x \, \widehat{\,} 2$$$", "$$$-10x\,\widehat{\,}+32$$$".

The following are valid $$$polynomial$$$ strings: "$$$3x\,\widehat{\,}3-2x\,\widehat{\,}2+4$$$" and "$$$4x-23+1+3-2-5x-10x\,\widehat{\,}-100$$$". But these are invalid $$$polynomial$$$ strings: "$$$+10x\,\widehat{\,}2$$$" and "$$$3x\,\widehat{\,}3+-2x\,\widehat{\,}4$$$".

The only characters in a valid $$$polynomial$$$ string are: digits ($$$0123456789$$$), plus sign($$$+$$$), minus sign ($$$-$$$), a lowercase letter x ($$$x$$$) and caret ($$$\,\widehat{ }\,$$$, this is ASCII 94 in input and output). There are no spaces even if the statement font make it seem like there are.

Input

A single line with a valid polynomial, the polynomial will consist of at most $$$100000$$$ characters and you are guaranteed that every coefficient and exponent will be at most $$$100$$$ in absolute value.

Output

A single line containing a valid polynomial, the derivative of the input polynomial. Additionally, you must:

  • Combine all terms that can be combined (Output "$$$2x \, \widehat{ } \, 3$$$" instead of "$$$10x \, \widehat{ } \, 3-8x\,\widehat{ } \, 3$$$")
  • Order the terms from smallest exponent to biggest exponent

The above restrictions guarantees the answer is unique.

Example
Input
4x-23+1+3-2-5x+10x^4-10x^-23+23+32x^-23
Output
-506x^-24-1+40x^3