# euclide.py

def euclide (a,b):
  if b<0: b=-b
  u=[]
  while b: u.append(a//b); (a,b)=(b,a%b)
  return u

def euclideconmcd (a,b):
  if b<0: b=-b
  u=[]
  while b: u.append(a//b); (a,b)=(b,a%b)
  return (u,a)

def inversomodn (a,n):
  u=soldiofante(a,n,1)
  if u==None: return None
  (x,y)=u; return x%n

def mcd (a,b):
  if b<0: b=-b
  while b: (a,b)=(b,a%b)
  return a

def mcde (a,b):
  if not b: return (a,1,0)
  if b<0: b=-b
  (d,x,y)=mcde(b,a%b); alfa=a//b
  return (d,y,x-alfa*y)

# [(p1,q1),(p2,q2),...]
def pq (*a):
  u=[]; (pkm1,pk,qkm1,qk)=(0,1,1,0)
  for alfa in a:
    (pkm1,pk,qkm1,qk)=(pk,alfa*pk+pkm1,qk,alfa*qk+qkm1)
    u.append((pk,qk))
  return u

def soldiofante (a,b,h):
  (listadeglialfa,d)=euclideconmcd(a,b)
  if h%d: return None
  s=h//d
  colonne=pq(*listadeglialfa); (v,u)=colonne[-2]
  n=len(listadeglialfa)
  if not n%2: v=-v
  else: u=-u
  return (u*s,v*s)