i64 gcd(i64 u, i64 v)
{
    register int shift;
    i64 diff;
    if (u == 0 || v == 0)
        return u | v;
    for (shift = 0; ((u | v) & 1) == 0; ++shift)
        u >>= 1, v >>= 1;
    while ((u & 1) == 0)
        u >>= 1;
    do
    {
        while ((v & 1) == 0)
            v >>= 1;
        if (u < v)
            v -= u;
        else
            diff = u - v, u = v, v = diff;
        v >>= 1;
    }
    while (v != 0);
    return u << shift;
}