dioff

pr<int, int> gcd(int a, int b, int xa, int ya, int xb, int yb)
{
    if (b == 0)
    {
        return {xa, ya};
    }
    int k = a / b;
    return gcd(b, a % b, xb, yb, xa - k * xb, ya - k * yb);
}

bool find_any_solution(int a, int b, int c, int &x0, int &y0) {
    int d = __gcd(a, b);
    if (c % d) {
        return 0;
    }
    auto solve = gcd(abs(a), abs(b), 1, 0, 0, 1);
    x0 = solve.first;
    y0 = solve.second;
    x0 *= c / d;
    y0 *= c / d;
    if (a < 0) x0 *= -1;
    if (b < 0) x0 *= -1;
    return 1;
}

void shift_solution(int &x, int &y, int a, int b, int cnt) {
    x += cnt * b;
    y -= cnt * a;
}