int gcd(int a, int b, int& x, int& y)
{
    int a1 = 1, a2 = 0;
    int b1 = 0, b2 = 1;

    while (b)
    {
        int k = a / b;
        a1 -= k * b1;
        a2 -= k * b2;
        a %= b;
        swap(a, b);
        swap(a1, b1);
        swap(a2, b2);
    }

    x = a1;
    y = a2;
    return a;
}