#-*- coding: utf-8 -*-
# pol.py
#
# polynomial calculation library
#
# A Polynomial a0 + a1 x + ... an x^n 
#   is Represented by [a0, a1, ..., an].
#
# The Zero Polynomial = []
# Degree of f = len(f) - 1

from math import *	
from sys import *
from cmath import *
from random import *

# Whether f is Zero Polynomial or not
def polzeroq(f):
    return (f == [])

# Degree of f
def deg(f):
    return len(f) - 1

# Set the Degree
# ( necessary after addition, subtraction and so on )
def cutzero(f):
    if f != []:
        while f[-1] == 0:
            del f[-1]
            if f == []:
                break
    return

# Copy of a Polynomial
def polcopy(f):
    return f[:]

# random polynomial of degree m, abs(coefficients) <= a
def randompol(m, a = 9):
    c = [randint(-a, a) for i in range(m + 1)]
    while c[m] == 0:
        c[m] = randint(-a, a)
    return c

# random monic polynomial of degree m, abs(coefficients) <= a
def randommonicpol(m, a):
    c = [randint(-a, a) for i in range(m)]
    c.append(1)
    return c

# Constant Polynomial
def constpol(a):
    if a == 0:
        return []
    else:
        return [a]

# Linear Polynomial a x + b
def linpol(a, b):
    return [b, a]

# Monomial x^n
def monomial(n):
    c = [0] * n
    c.append(1)
    return c

# Derivative
def polder(f):
    if deg(f) <= 0:
        return []
    else:
        c = []
        for i in range(1, len(f)):
            c.append(i * f[i])
        return c

# Scalar Multiplication
def polscmul(a, f):
    return [a * x for x in f]

def polconstmul(a, f):
    return polscmul(a, f)

# Addition
def poladd(f, g):
    if polzeroq(f):
        return polcopy(g)
    if polzeroq(g):
        return polcopy(f)
    m = deg(f)
    n = deg(g)
    c = []
    if m >= n:
        for i in range(n + 1):
            c.append(f[i] + g[i])
        for i in range(n + 1, m + 1):
            c.append(f[i])
        cutzero(c)
    else:
        for i in range(m + 1):
            c.append(f[i] + g[i])
        for i in range(m + 1, n + 1):
            c.append(g[i])
    return c

# Subtraction
def polsub(f, g):
    if polzeroq(f):
        return polcopy(g)
    if polzeroq(g):
        return polcopy(f)
    m = deg(f)
    n = deg(g)
    c = []
    if m >= n:
        for i in range(n + 1):
            c.append(f[i] - g[i])
        for i in range(n + 1, m + 1):
            c.append(f[i])
        cutzero(c)
    else:
        for i in range(m + 1):
            c.append(f[i] - g[i])
        for i in range(m + 1, n + 1):
            c.append(-g[i])
    return c  

# Multiplication
def polmul(f, g):
    if polzeroq(f) or polzeroq(g):
        return []
    m = deg(f)
    n = deg(g)
    c = [0] * (m + n + 1)
    for i in range(m + 1):
        a = f[i]
        for j in range(n + 1):
            c[i + j] = c[i + j] + (a * g[j])
    return c

# Division by Monic Polynomial
def poldivmonic(f, g):
    m = deg(f)
    n = deg(g)
    r = polcopy(f)
    if m < n:
        return [[], r]
    else:
        k = m - n
        q = []
        for i in range(m, n - 1, -1):
            a = r[i]
            q = [a] + q
            for j in range(n + 1):
                r[i - j] -= a * g[n - j]
    cutzero(r)
    return [q, r]

# round the coefficients
def polround(f):
    return [int(round(x)) for x in f]

# evaluate f(x) at x = a
def poleval(f, a):
    w = 0
    d = deg(f)
    for i in range(d, -1, -1):
        w = a * w + f[i]
    return w

# quotient f(x) / (x - a)  when  f(x) has a factor x - a
def poldivlinfac(f, a):
    c = []
    k = 0
    for i in range(deg(f), 0, -1):
        k = f[i] + a * k
        c = [k] + c
    return c

# Newton method: one of the roots of  f(x) = 0 
def polnewton(f):
    seed()          # randomize
    e = 1e-12       # addmissible error
    g = polder(f)
    ok = False
    while not ok:
        a = 0
        b = complex(random(), random())  # initial value
        m = 0
        while m < 1024:         # maximal repeating
            a = b
            b = a - poleval(f, a) // poleval(g, a)
            m += 1
            if abs(a - b) <= e:
                ok = True
                break   
    return b

# all of the roots of  f(x) = 0
def polroots(f):
    f = polcopy(f0)
    r = []
    while deg(f) > 0:
        a = polnewton(f)
        f = poldivlinfac(f, a)
        r.append(a)
        # delete # of the next line to trace
        #complexpolwrite(f); print 
    return r

# String for  f  with Real Coefficients
def realpolstr(f, v = 'x'):
    if polzeroq(f):
        return '0'
    s = ''
    d = deg(f)
    for i in range(d, -1, -1):
        c = f[i]
        if c != 0:
            if c > 0:
                if i < d:
                    s = s + ' + '
            else:
                s = s + ' - '
            c = abs(c)
            if c != 1 or i == 0:
                s = s + ('%f' % c)
                if i > 0:
                    s = s + ' * '
            if i > 1:
                s = s + v + ('^%d' % i)
            if i == 1:
                s = s + v
    return s

# String for  f  with Complex Coefficients
def complexpolstr(f, v = 'x'):
    if polzeroq(f):
        return '0'
    s = ''
    d = deg(f)
    for i in range(d, -1, -1):
        c = f[i]
        if c != complex(0, 0):
            if i < d:
                s = s + ' + '
            if c != 1 or i == 0:
                s = s + ('%s' % c)
                if i > 0:
                    s = s + ' '
                    #s = s + ' * '
            if i > 1:
                s = s + v + ('^%d' % i)
            if i == 1:
                s = s + v
    return s

# String for  f  with Integral Coefficients
# （ with no space： for the maxima input and so on）
def intpolstrnosp(f, v = 'x'):
    if polzeroq(f):
        return '0'
    s = ''
    d = deg(f)
    for i in range(d, -1, -1):
        c = f[i]
        if c != 0:
            if c > 0:
                if i < d:
                    s = s + '+'
            else:
                s = s + '-'
            c = abs(c)
            if c != 1 or i == 0:
                s = s + ('%d' % c)
                if i > 0:
                    s = s + '*'
            if i > 1:
                s = s + v + ('^%d' % i)
            if i == 1:
                s = s + v
    return s

# String for  f  with Integral Coefficients
def intpolstr(f, v = 'x'):
    if polzeroq(f):
        return '0'
    s = ''
    d = deg(f)
    for i in range(d, -1, -1):
        c = f[i]
        if c != 0:
            if c > 0:
                if i < d:
                    s = s + ' + '
            else:
                s = s + ' - '
            c = abs(c)
            if c != 1 or i == 0:
                s = s + ('%d' % c)
                if i > 0:
                    s = s + ' * '
            if i > 1:
                s = s + v + ('^%d' % i)
            if i == 1:
                s = s + v
    return s

def polstr(f, v = 'x'):
    return intpolstr(f, v)
        
def fppolstr(f, v = 'x'):
    if polzeroq(f):
        return '0'
    s = ''
    d = deg(f)
    for i in range(d, -1, -1):
        if f[i]:
            if i < d:
                s = s + ' + '
            if i > 1:
                if f[i] > 1:
                    s = s + ('%d ' % f[i]) 
                s = s + v + ('^%d' % i)    
            if i == 1:
                if f[i] > 1:
                    s = s + ('%d ' % f[i]) 
                s = s + v
            if i == 0:
                s = s + ('%d' % f[0])
    return s

# Output
def realpolwrite(f, v = 'x'):
    print(realpolstr(f, v), end = ' ')
    return

# + line feed
def realpolwriteln(f, v = 'x'):
    print(realpolstr(f, v))
    return

def complexpolwrite(f, v = 'x'):
    print(complexpolstr(f, v), end = ' ')
    return

def complexpolwriteln(f, v = 'x'):
    print(complexpolstr(f, v))
    return

def intpolwrite(f, v = 'x'):
    print(intpolstr(f, v), end = ' ')
    return

def intpolwriteln(f, v = 'x'):
    print(intpolstr(f, v))
    return

def intpolwritenosp(f, v = 'x'):
    print(intpolstrnosp(f, v), end = ' ')
    return

def intpolwritelnnosp(f, v = 'x'):
    print(intpolstrnosp(f, v))
    return

def fppolwrite(f, v = 'x'):
    print(fppolstr(f, v), end = ' ')
    return

def fppolwriteln(f, v = 'x'):
    print(fppolstr(f, v))
    return

def polwrite(f, v = 'x'):
    intpolwrite(f, v)
    return

def polwriteln(f, v = 'x'):
    intpolwriteln(f, v)
    return

def numbercharq(c):
    return (c >= '0' and c <= '9')

# String -> Polynomial
#   string must be written in descending powers
#   asterisk mark is ignored
#     3 * x^2 - 5 * x + 2 -> [2, -5, 3] 
#     3 x^2 - 5 x + 2     -> [2, -5, 3] 
def string2pol(s):
    if s == '0':
        return []
    
    if s.find('x') < 0:
        return [int(s)]

    a = 0
    sgn = 1
    f = True    # whether 'x' appears for the first time
    while len(s) > 0:
        t = s[0]
        s = s[1:]
        if t == '-':
            sgn = -1
        if numbercharq(t):
            a = 10 * a + int(t)
        if t == 'x':
            if f:
                f = False
                if len(s) == 0:
                    hd = 1      # highest degree
                else:
                    if s[0] != '^':
                        hd = 1
                    else:
                        s = s[1:]
                        hd = 0
                        while numbercharq(s[0]):
                            hd = 10 * hd + int(s[0])
                            s = s[1:]
                            if len(s) == 0:
                                break
                c = [0] * (hd + 1)
                if a == 0:
                    c[hd] = sgn
                else:
                    c[hd] = sgn * a
                a = 0
                sgn = 1
            else:
                if len(s) == 0:
                    d = 1      # degree
                else:
                    if s[0] != '^':
                        d = 1
                    else:
                        s = s[1:]
                        d = 0
                        while numbercharq(s[0]):
                            d = 10 * d + int(s[0])
                            s = s[1:]
                            if len(s) == 0:
                                break
                if a == 0:
                    c[d] = sgn
                else:
                    c[d] = sgn * a
                a = 0
                sgn = 1
    if a != 0:
        c[0] = sgn * a
    return c

# input a polynomial
def polinput():
    d = eval(input("次数 = "))
    c = []
    for i in range(d,-1,-1):
        print(i, end = '')
        a = eval(input("次の係数 = "))
        c = [a] + c
    return c

# real part of a complex number
def re(z):
    return z.real

# imaginary part of a complex number
def im(z):
    return z.imag