Description

A univariate polynomial of degree $n$ can be written as:

$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$$

Here, $a_ix^i$ is called the $i$-th degree term, and $a_i$ is its coefficient. Given the degree and coefficients of a univariate polynomial, output the polynomial in the following format:

1. The indeterminate is $x$. List the terms from left to right in descending order of degree.
2. Include only terms whose coefficients are nonzero.
3. If the leading (degree-$n$) coefficient is positive, the polynomial must not start with a + sign; if it is negative, the polynomial must start with a - sign.
4. For any non-leading term, connect it to the previous term with + or -, indicating a positive or negative coefficient, respectively. Immediately follow with the absolute value of the coefficient as a positive integer (for terms of degree greater than $0$, omit the $1$ if the coefficient’s absolute value is $1$). If the exponent of $x$ is greater than $1$, write it as “$x^b$”, where $b$ is the exponent; if the exponent is $1$, write it as $x$; if the exponent is $0$, output only the coefficient.
5. There must be no extra spaces at the beginning or the end of the polynomial.

Input Format

There are $2$ lines of input.

• The first line contains one integer $n$, the degree of the polynomial.
• The second line contains $n+1$ integers. The $i$-th integer is the coefficient of the term of degree $n-i+1$. Integers are separated by single spaces.

Output Format

Output one line: the polynomial formatted as described above.

5 
100 -1 1 -3 0 10

100x^5-x^4+x^3-3x^2+10

3 
-50 0 0 1 

-50x^3+1 

Hint

NOIP 2009 Junior, Problem 1.

Constraints: For 100% of the testdata, $0 \le n \le 100$, and $-100 \le a_i \le 100$.

$\text{upd 2022.8.1}$: A new set of hack testdata has been added.

Translated by ChatGPT 5