from math import
# d = gcd(a,b) = ax+by となる d,x,y を求め、
# ３つの要素を持つ配列 [d,x,y] を返り値にする
# 返り値の使い方は main routine の５行目以降を参照
def euclid(a,b):
if b == 0:
if a >= 0:
return [a,1,0]
else:
return [-a,-1,0]
else:
r0 = a
r1 = b
x0 = 1
x1 = 0
y0 = 0
y1 = 1
while r1 != 0:
q = r0/r1
##### ここを埋めよ #####
r0 = r1
r1 = r2
x0 = x1
x1 = x2
y0 = y1
y1 = y2
if r0 < 0:
r0 = -r0
x0 = -x0
y0 = -y0
return [r0,x0,y0]