// -----------------------------------------------------------------------------
// The extended Euclidean algorithm computes for given integers a,b numbers g,
// u and v such that g = gcd(a,b) = u*a + v*b holds. It also computes numbers
// s and t such that 0 = s*a + t*b holds.
// -----------------------------------------------------------------------------

function ExtEuclid(int a,b):int {
    int q;
    int m,n,u,v,s,t;
    int m1,n1,u1,v1;
    
    m = a;
    n = b;
    u = +1;
    v = +0;
    s = +0;
    t = +1;
    assert(m == (u*a + v*b));
    assert(n == (s*a + t*b));

    // The loop maintains the following invariants:
    //    (1) m == u*a + v*b
    //    (2) n == s*a + t*b
    //    (3) gcd(m,n) = gcd(a,b)
    // Note that (3) is invariant since gcd(m,n) = gcd(n,m%n), and the other
    // invariants are immediately seen by expanding the assignments.
    
    while(n!= +0) {
        q = m / n;
        m1 = n;
        n1 = m - q * n;
        u1 = s;
        v1 = t;
        s = u - q * s;
        t = v - q * t;
        m = m1;
        n = n1;
        u = u1;
        v = v1;
        assert(m == (u*a + v*b));
        assert(n == (s*a + t*b));
    }
    // since n=0 holds, we conclude the following from the invariants
    //    (1) m == u*a + v*b
    //    (2) 0 == s*a + t*b
    //    (3) gcd(m,0) = m = gcd(a,b)
    return m;
}


thread main {
    int g;
    g = ExtEuclid(+75025,+46368);
}