def succ(x):
    return x + 1

def isum(x,y):
    u,v = x,0
    while v!=y: u,v = succ(u),succ(v)
    return u

def iprod(x,y):
    u,v = 0,0
    while v!=y: u,v = isum(u,x),succ(v)
    return u

def ipower(x,y):
    u,v = 1,0
    while v!=y: u,v = iprod(u,x),succ(v)
    return u

def idiff(x,y):
    u,v,w = 0,x,y
    while v!=y and w!=x: u,v,w = succ(u),succ(v),succ(w)
    return u,v,w

def leq(x,y):
    return idiff(x,y)[1]==y

def geq(x,y):
    return idiff(x,y)[2]==x

def difference(x,y):
    return idiff(x,y)[0]

def quotres(a,b):
    q,d = 0,idiff(a,b)
    while d[2]==a: q,a,d=succ(q),d[0],idiff(d[0],b)
    return [q,a]

def repres(a,g):
    result = [a]
    while leq(g,result[0]): result[:1] = quotres(result[0],g)
    return result

def nat(nrlist,g):
    def sumg(a,b): return isum(iprod(a,g),b)
    return reduce(sumg,nrlist)

def remove0(nrlist):
    while nrlist[0]==0 and nrlist!=[0]: del nrlist[0]
    return nrlist

def normalize(nrlist,g):
    normalform=[]
    while nrlist!=[]:
        qr=quotres(nrlist.pop(),g)
        if nrlist!=[]: nrlist[-1]=isum(nrlist[-1],qr[0])
        elif qr[0]!=0: nrlist=[qr[0]]
        normalform.insert(0,qr[1])
    return remove0(normalform)

def equalize(nrlist1,nrlist2):
    list1,list2 = [0 for i in nrlist1],[0 for i in nrlist2]
    nrlist1=list2+nrlist1
    nrlist2=list1+nrlist2
    while nrlist1!=[0] and nrlist2!=[0] and\
    nrlist1[0]==nrlist2[0]==0:
        del nrlist1[0]
        del nrlist2[0]
    return (nrlist1,nrlist2)

def gsum(nrlist1,nrlist2,g):
    (nrlist1,nrlist2) = equalize(nrlist1,nrlist2)
    sums = []
    while nrlist1!=[]:
        sums.append(isum(nrlist1.pop(0),nrlist2.pop(0)))
    return normalize(sums,g)

def gprod(nrlist1,nrlist2,g):
    products = [[iprod(i,j) for j in nrlist2] for i in nrlist1]
    def sum1(list1,list2): return gsum(list1+[0],list2,g)
    return normalize(reduce(sum1,products),g)

def lesseq(nrlist1,nrlist2):
    (nrlista,nrlistb)=equalize(nrlist1,nrlist2)
    while nrlista!=[] and nrlista[0]==nrlistb[0]:
        del nrlista[0]
        del nrlistb[0]
    if nrlista==[]: return True
    else: return leq(nrlista[0],nrlistb[0])

def sub0(nrlist1,nrlist2,g):
    (nrlist1,nrlist2)=equalize(nrlist1,nrlist2)
    diffs = []
    while nrlist1!=[]:
        diffs.append(difference(isum(nrlist1.pop(0),g),
        succ(nrlist2.pop(0))))
    diffs[-1]=succ(diffs[-1])
    diffs = normalize(diffs,g)
    diffs[:1]=[]
    return diffs

def sub(nrlist1,nrlist2,g):
  return remove0(sub0(nrlist1,nrlist2,g))

def gmultiples(nrlist,g):
    mults = [[0,[0]]]
    h = difference(g,1)
    while mults[-1][0]!=h:
        s = succ(mults[-1][0])
        mults.append([s,gprod([s],nrlist,g)])
    return mults

def gdivmod0(nrlist1,nrlist2,g):
    lista = [[0,[0]]]
    listb = gmultiples(nrlist2,g)[1:]
    while listb!=[] and lesseq(listb[0][1],nrlist1):
        lista.append(listb.pop(0))
    return [lista[-1][0],sub0(nrlist1,lista[-1][1],g)]

def gdivmod(nrlist1,nrlist2,g):
    nrlist1copy = nrlist1[:]
    nrlist2copy = nrlist2[:]
    rlist = []
    dlist = []
    qlist = []
    while nrlist1copy!=[] and nrlist2copy!=[]:
        rlist.append(nrlist1copy.pop(0))
        dlist.append(nrlist2copy.pop(0))
    if nrlist2copy!=[]: return [[0],nrlist1]
    else:
        while nrlist1copy!=[]:
            qr = gdivmod0(rlist,dlist,g)
            qlist.append(qr[0])
            rlist = qr[1]
            rlist.append(nrlist1copy.pop(0))
        qr = gdivmod0(rlist,dlist,g)
        qlist.append(qr[0])
        rlist = qr[1]
        return [remove0(qlist),remove0(rlist)]

def convert(nrlist,g1,g2):
    result = [nrlist]
    g = repres(g2,g1)
    while lesseq(g,result[0]):
        result[:1] = gdivmod(result[0],g,g1)
    return [nat(i,g1) for i in result]