void abort() { };

                        
                                                                                                                                                          
                                                                      
extern unsigned __VERIFIER_nondet_uint();
                        
/*@ 
    requires (1);
    ensures ((cond != 0));
@*/
void assume_abort_if_not(int cond) {
  if(!cond) {abort();}
}
/*@ 
    requires ((cond == 1)) && (cond != 0);
    ensures ((cond == 1)) && (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();
    assume_abort_if_not(a>=0 && a<=1);
    b = __VERIFIER_nondet_uint();
    assume_abort_if_not(b>=0 && b<=1);
    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 (((((((a == v) && (b == y)) && (b == u)) && (y == 1)) && (x == 1)) && (a == x)));
@*/
    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;
}