#-*- coding: utf-8 -*-
#
# pol.py
# polynomial calculation library
# 2010.5.17 ver.

#   f = [d, [c[0], c[1], ..., c[d]]
# represents the polynomial
#   f(x) = c[d] x^d + ... + c[1] * x + c[0]
# zero polynomial = [-1, []]

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

# weather f is zero polynomial or not
def polzeroq(f):
        return (f[0] == -1)

# set the degree
# ( necessary after addition, subtraction and so on ) 
def truedeg(f):
        c = f[1]
        while len(c) > 0 and c[-1] == 0:
                c = c[:-1]
        if len(c) == 0:
                f[0] = -1
                f[1] = []
        else:
                f[0] = len(c) - 1
                f[1] = c
        return

def poldeg(f):
        return f[0]

def polcoeff(f, i):
        return f[1][i]

# convert a list of nembers to polynomial 
def list2pol(c):
        m = len(c)
        return [m - 1, c]

# copy a polynomial
def polcopy(f):
        if polzeroq(f):
                return [-1, []]
        g = []
        g.append(f[0])
        c = []
        for i in range(0, f[0] + 1):
                c.append(f[1][i])
        g.append(c)
        return g

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

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

# constant polynomial
def constpol(a):
        if a != 0:
                return [0, [a]]
        else:
                return [-1, []]

# linear polynomial ax+b
def linpol(a, b):
        return [1, [b, a]]

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

# derivative
def polder(f):
        if f[0] <= 0:
                return [-1, []]
        else:
                m = f[0]
                c = []
                for i in range(1, m+1):
                        c.append(i * f[1][i])
                return [m - 1, c]

# constant multiple
def polconstmul(a, f):
        if polzeroq(f):
                return [-1, []]
        c = []
        m = f[0]
        for i in range(0, m+1):
                c.append(a * f[1][i])
        return [m, c]

# addition
def poladd(f, g):
        if polzeroq(f):
                return g
        if polzeroq(g):
                return f
        m = f[0]
        n = g[0]
        c = []
        if m >= n:
                for i in range(0, n + 1):
                        c.append(f[1][i] + g[1][i])
                for i in range(n + 1, m + 1):
                        c.append(f[1][i])
                h = [m, c]
                truedeg(h)
        else:
                for i in range(0, m + 1):
                        c.append(f[1][i] + g[1][i])
                for i in range(m + 1, n + 1):
                        c.append(g[1][i])
                h = [n, c]
        return h

# subtraction
def polsub(f, g):
        if polzeroq(f):
                return g
        if polzeroq(g):
                return f
        m = f[0]
        n = g[0]
        c = []
        if m >= n:
                for i in range(0, n + 1):
                        c.append(f[1][i] - g[1][i])
                for i in range(n + 1, m + 1):
                        c.append(f[1][i])
                h = [m, c]
                truedeg(h)
        else:
                for i in range(0, m + 1):
                        c.append(f[1][i] - g[1][i])
                for i in range(m + 1, n + 1):
                        c.append(-g[1][i])
                h = [n, c]
        return h  

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

# round the coefficients
def polround(f):
        c = []
        m = f[0]
        for i in range(0, m + 1):
                c.append(int(round(f[1][i])))
        return [m, c]

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

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

# division by monic polynomial
def poldivmonic(f, g):
        m = f[0]
        n = g[0]
        if m < n:
                return [[-1, []], f]
        else:
                k = m - n
                q = [k]
                qc = []
                r = polcopy(f)
                for i in range(m, n - 1, -1):
                        a = r[1][i]
                        qc = [a] + qc
                        for j in range(0, n + 1):
                                r[1][i - j] -= a * g[1][n - j]
                q.append(qc)
        truedeg(r)
        return [q, r]

# 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):
        r = []
        while f[0] > 0:
                a = polnewton(f)
                f = poldivlinfac(f,a)
                r.append(a)
                # delete # of the next line to trace
                #complexpolwrite(f); print 
        return r

# output a polynomial with real coefficients
def polwrite(f):
        d = f[0]
        for i in range(d,-1,-1):
                c = f[1][i]
                if c != 0:
                        if c > 0:
                                if i < d:
                                        print "+",
                        else:
                                print "-",
                        c = abs(c)
                        if c != 1 or i == 0:
                                print c,
                        if i > 1:
                                print "x^%d" % i,
                        if i == 1:
                                print "x",

# + line feed
def polwriteln(f):
        polwrite(f)
        print

# output a polynomial with integral coefficients
# （ with no space： for the maxima input and so on）
def intpol2string(f):
        s = ''
        d = f[0]
        for i in range(d,-1,-1):
                c = f[1][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 + ("x^%d" % i)
                        if i == 1:
                                s = s + "x"
        return s

# output a polynomial with integral coefficients
def intpol2stringwithspace(f):
        s = ''
        d = f[0]
        for i in range(d,-1,-1):
                c = f[1][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 + ("x^%d" % i)
                        if i == 1:
                                s = s + "x"
        return s

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

def string2pol(s):
    if s.find("x") < 0:
        a = int(s)
        return [0, [a]]

    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 [hd, c]
                                
# output a polynomial with complex coefficients
def complexpolwrite(f):
        d = f[0]
        for i in range(d,-1,-1):
                c = f[1][i]
                if c != 0:
                        if c != 0:
                                if i < d:
                                        print "+",
                        print c,
                        if i > 1:
                                print "x^%d" % i,
                        if i == 1:
                                print "x",

# input a polynomial
def polinput():
        d = input("次数 = ")
        c = []
        for i in range(d,-1,-1):
                print i,
                a = input("次の係数 = ")
                c = [a] + c
        return [d,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