def div(a,b): #norim, kad nebutu stufo, tokio kaip 0.0, o butu vietoj to sveikieji
        if float(a)/b==a/b: return a/b
        return float(a)/b
def gcd(*args): #rasime skaiciu DBD
        def gcd_of_two(a,b):
            a,b=abs(a),abs(b)
            while a>0:
                if b>a: a,b=b,a
                if a==1: return 1
                a-=(a/b)*b
            return b
        return reduce(lambda x,y: gcd_of_two(x,y), args)
def unit(length, diagonal=[]):
    if diagonal==[]: diagonal=[1]*length
    return [tuple(int(i==j)*diagonal[i] for i in range(length)) for j in range(length)] #vienetine matrica
def inverse(matrix): #atvirkstines matricos algoritmas
    #EXAMPLE: [[a1,a2,x1,x2],[b1,b2,y1,y2]] ->[[a3,a4,a5,a6],[x3,x4,x5,x6]], nes tai ekvivalentu zingsniui
    # /a1 a2\|/1 0 x1 x2\  _______\     /1 0\|/a3 a4 a5 a6\
    # \b1 b2/|\0 1 y1 y2/         /     \0 1/|\x3 x4 x5 x6/
    #rows can be longer than len of matrix; that case last terms means solutions to several systems of equations
    M=[[m for m in n] for n in matrix] #SIDE EFFECTS ARE ELIMINATED IN THIS ROW
    U=unit(len(M))
    order=[(i,j) for i in range(len(M)-1) for j in range(i+1,len(M))]+[(i,j) for i in range(len(M)-1,0,-1) for j in range(i-1,-1,-1)]
    #eiluciu keitimo tvarka, kai reikia suvesti i trikampi, po to i diagolini pavidala
    for i in range(len(M)):
        U[i]=U[i]+tuple(M[i][len(matrix):len(M[0])])
    #eiluciu sudejimo eiliskumas
    try:
        for n in order:
            i,j=n[0],n[1]
            if M[i][i]==0: # jei pasitaike nulinis elementas ant istrizaines, keiciame matricos eilutes. Jei neradome, ka sukeisti - nera atvirkstines matricos
                p=0
                for k in range(i+1,len(M)):
                    if M[k][i]<>0:
                        M[i],M[k]=M[k],M[i]
                        U[i],U[k]=U[k],U[i]
                        p=1
                        break
                if p==0: return [M[i] for i in range(len(M)) if M[i][i]<>0] #bug we'll use later
            if M[j][i]<>0: #suvedimo i trikampi pavidala vienas zingsnis, kai uznulinama kazkuri eilute
                c=M[i][i]*M[j][i]/gcd(M[i][i], M[j][i])
                c1,c2=c/M[i][i],c/M[j][i]
                M[j]=tuple(map(lambda x: x[1]*c1-x[0]*c2, zip(M[j],M[i])))
                U[j]=tuple(map(lambda x: x[1]*c1-x[0]*c2, zip(U[j],U[i])))
        return map(lambda i: tuple(map(lambda x: div(x, M[i][i]),U[i])), range(len(U)))
    except IndexError: print 'Nesiskaiciuoja inverse, per daug eiluciu matricoje'
def solve_system(matrix): return [list(n) for n in zip(*inverse(matrix))[len(matrix):]]
def interpolation(ordered_pairs):
    n=len(ordered_pairs)
    return solve_system([[m[0]**i for i in range(n)]+[m[1]] for m in ordered_pairs])