Oh, these brackets#2337
Sign in

Oh, these brackets

1 second
64 megabytes
Hard

The mathematical expression is given as a product:

(\pm a_{2}x^{2} \pm a_{1}x \pm a_{0}) \cdot (\pm b_{2}x^{2} \pm b_{1}x \pm b_{0}) \cdot (\pm c_{2}x^{2} \pm c_{1}x \pm c_{0}) \cdots

Each of the bracketed factors contains an expression of the form \pm a_{2}x^{2} \pm a_{1}x \pm a_{0}, where at least one coefficient a_i (b_i, c_i, and so on) is nonzero.

Your task is to write a program that multiplies the bracketed expressions and outputs the resulting function as a polynomial, combining like terms by powers of , i.e.:

\pm q_{2N}x^{2N} \pm q_{2N-1}x^{2N-1} \cdots \pm q_{3}x^{3} \pm q_{2}x^{2} \pm q_{1}x \pm q_{0}

Input

The first line of input contains the number (1 \leq N \leq 6).

The second line contains an expression with pairs of brackets. Inside each pair is an expression of the form \pm a_{2}x^{2} \pm a_{1}x \pm a_{0}, where is either a "+" or "-" sign. If any coefficient is zero, that coefficient, its corresponding , and the sign are omitted. If a_i = \pm 1 and i > 0, the one is not written before its . If the last (by index) coefficients are zero and the next coefficient is positive, the "+" sign is not written in front of it. Each coefficient a_i does not exceed in absolute value.

There are no arbitrary whitespace characters (spaces, tabs) in the expression. The input ends with a newline character. If you have questions about the input format, refer to the examples in the problem statement.

Output

On the first line of output, print the result of expanding the brackets in the given expression in the following format:

\pm q_{2N}x^{2N} \pm q_{2N-1}x^{2N-1} \cdots \pm q_{3}x^{3} \pm q_{2}x^{2} \pm q_{1}x \pm q_{0}

following the input description.

Follow the format shown in the examples as closely as possible.

Examples

Example 1

Loading
Loading