Problem:
Extended Euclid Algorithm   Given positive integers a and b , find the integer solution ( x , y ) to ax + by = gcd(a, b) , where gcd(a, b) is the greatest common divisor of a and b .  Input   a  b   Two positive integers a and b are given separated by a space in a line.  Output  Print two integers x and y separated by a space. If there are several pairs of such x and y , print that pair for which |x| + |y| is the minimal (primarily) and x ≤ y (secondarily).  Constraints   1 ≤ a , b ≤ 10 9   Sample Input 1  4 12  Sample Output 1  1 0   Sample Input 2  3 8  Sample Output 2  3 -1

Solution (Python):
import sys


sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]


def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return(lastx, lasty, a)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv, q

def main():
    a, b = li_input()
    x, y = modinv(a, b)
    print(x, y)


main()

Solution (Python):
def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q = m // n
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, m - q * n
    return x2, y2  
print(*extended_euclid(*map(int, input().split())))