void abort() { };

                        
                                                                                                                                                          
                                                                      
extern unsigned __VERIFIER_nondet_uint();
                        
void assume_abort_if_not(int cond) {
  if(!cond) {abort();}
}
/*@ 
    requires ((1 <= cond)) && (cond != 0);
    ensures ((1 <= cond)) && (1);
@*/
void __VERIFIER_assert(int cond) {
    if (!(cond)) {
    ERROR:
        {/*@ assert(0); */;}
    }
    return;
}

int main() {
    unsigned a, b;
    unsigned x, y, u, v;
    a = __VERIFIER_nondet_uint();
    b = __VERIFIER_nondet_uint();
    assume_abort_if_not(a >= 1); //inf loop if remove
    assume_abort_if_not(b >= 1);

    assume_abort_if_not(a <= 65535);
    assume_abort_if_not(b <= 65535);

    x = a;
    y = b;
    u = b;
    v = a;

/*@
loop invariant ((((((unsigned long long) b * a) % 2147483648) * 2) == (((__int128) ((unsigned long long) y * v) + ((unsigned long long) x * u)) % 4294967296)));
@*/
    while (1) {
        __VERIFIER_assert(x*u + y*v == 2*a*b);

        if (!(x != y))
            break;

        if (x > y) {
            x = x - y;
            v = v + u;
        } else {
            y = y - x;
            u = u + v;
        }
    }

    __VERIFIER_assert(x*u + y*v == 2*a*b);
    // x == gcd(a,b)
    //(u + v)/2==lcm(a,b)

    return 0;
}