def pivot(v, u, t):
    return u-t*v

def printVector(v):
    s = ""
    for i in [0..len(v)-1]:
        if v[i] != 0: s = s+ "("+ str(i)+","+str(v[i])+")"
    print s

def dimension(L):
    A = matrix(L)
    V = A.image()
    return dim(V)

def isNotZero(field, v):
    V = VectorSpace(field,len(v))
    u = V.zero()
    return u != v

def lg(v):
    k = 0
    for i in [0..len(v)-1]:
        if v[i] != 0: k = i+1
    return k

def order(v, w):
    if lg(v) > lg(w): return int(-1)
    elif lg(v) == lg(w): return int(0)
    else: return int(1)

def leadingVector(L):
    v = L[0]
    for i in [1..len(L)-1]:
        if lg(L[i]) > lg(L[i-1]): v=L[i]
    return v

def sort(field, L, v):
    k, G = lg(v), []
    g = lambda v: isNotZero(field,v)
    for i in [0..len(L)-1]:
         G = G+[pivot(v,L[i],L[i][k-1]/v[k-1])]
    return filter(g,G)+[v]

def sortedList(field, L):
    G = sort(field,L,leadingVector(L))
    G.sort(cmp = order)
    return G

def orderedBasis(field, L):
    n, G = dimension(L), sortedList(field, L)
    for i in [1..n-1]:
        G = sort(field, G, G[i])
        G.sort(cmp = order)
    return G


def reverseReducedBasis(field, L):
    G = orderedBasis(field, L)
    n = len(G)
    H = []
    for i in [0..n-1]:
        v, k = G[i], lg(G[i])
        H = H+[1/v[k-1]*v]
    return H

def reducedBasis(field, L):
    if L == []: return L
    else: G = reverseReducedBasis(field, L); G.reverse(); return G

def operator(field, G):
    L = reducedBasis(field, G)
    n = len(L[0])
    V = VectorSpace(QQ,n)
    v = V.zero()
    G = (lg(L[0])-1)*[v]+[L[0]]
    k = len(L)
    for i in [1..k-1]:
        G = G+(lg(L[i])-lg(L[i-1])-1)*[v]+[L[i]]
    G = G+(n-lg(L[k-1]))*[v]
    return identity_matrix(field,n)-matrix(G).transpose()

def lowerBound(field, T_1, T_2):
    V_1, V_2 = kernel(T_1.transpose()), kernel(T_2.transpose())
    G_1, G_2 = basis(V_1),basis(V_2)
    L_1, L_2 = reducedBasis(field, G_1), reducedBasis(field, G_2)
    G = L_1+L_2
    L = reducedBasis(field, G)
    return operator(field, L)

def upperBound(field, T_1, T_2):
    V_1, V_2 = kernel(T_1.transpose()), kernel(T_2.transpose())
    V = V_1.intersection(V_2)
    G = basis(V)
    L = reducedBasis(field, G)
    return operator(field, L)

def tilde(field, T):
    n, L = T.nrows(),[]
    for i in [0..n-1]:
        j, k = i, n-i-1
        if T[i,i] == 1: L = L+[vector(j*[0]+[1]+k*[0])]
    return operator(field, L)

def complement(field, L):
    n, C, T = len(L), L[0], tilde(field, L[0])
    for i in [1..n-1]: C = lowerBound(field, C, L[i])
    for j in [1..n-1]: T = upperBound(field, T, tilde(field, L[j]))
    return upperBound(field, C, T)

def printOperator(field, U):
    F = reducedBasis(field, kernel(U.transpose()).basis())
    for i in [0..len(F)-1]:
        printVector(F[i])