void Gcd(int64 a, int64 b, int64* res) {
    int64 U[3] = { a, 1, 0 }, V[3] = { b, 0, 1 }, T[3], q, temp;
    while (V[0] != 0)
    {
        q = U[0] / V[0];
        T[0] = U[0] % V[0]; T[1] = U[1] - q*V[1]; T[2] = U[2] - q*V[2];
        U[0] = V[0]; U[1] = V[1]; U[2] = V[2];
        V[0] = T[0]; V[1] = T[1]; V[2] = T[2];
    }
    res[0] = U[0]; res[1] = U[1]; res[2] = U[2];
}