Tidy the Blackboard Polynomial

Students scribble polynomials in x on the blackboard, and the teacher wants each one rewritten in a single tidy form. Write tidy_polynomial(expr) that combines like terms and returns the tidy string.

Input. expr is one or more terms joined by + or -. The first term may have its own leading + or -. A term is one of:

• a constant c, such as 7;
• cx or x (coefficient 1), meaning c * x;
• cx^e or x^e, meaning c * x**e.

Here c and e are non-negative decimal integers (x^0 is just 1, x^1 is x, and 0x^5 is zero). Spaces may appear between any two symbols, but never inside a number.

Output. Keep only the exponents whose combined coefficient is not zero, highest exponent first. Write the first term with a leading - if it is negative (no sign if positive), and join the rest with " + " or " - ". For each term write the absolute coefficient, omit it when it is 1 and the exponent is at least 1, then x^e (exponent at least 2), x (exponent 1) or nothing (exponent 0). If every coefficient cancels, return "0".

Examples

Input:  expr = "3x^2 - x + 2x^2 + 5 - 7"
Output: "5x^2 - x - 2"

Input:  expr = "-4 + x^0 + 2x^1 + 0x^9"
Output: "2x - 3"

Input:  expr = " - x^10 + 1x^10 - 3 x"
Output: "-3x"

Input:  expr = "x - x"
Output: "0"

Constraints

• 1 <= len(expr) <= 10**6 and expr is always well formed
• 0 <= c <= 10**9 and 0 <= e <= 10**12

Goals

• Split a signed sum into terms and read each term's coefficient and exponent
• Combine like terms in a dict keyed by exponent, not a list indexed by it
• Print a unique tidy form, including the all-cancelled case