def extgcd(a, b): if b: d, y, x = extgcd(b, a%b) y -= (a/b)*x return d, x, y else: return a, 1, 0 inputs = lambda:map(int, raw_input().split()) p, q = inputs() if p