ll get_gcd(ll a, ll b) { if (b == 0) return a; return get_gcd(b, a % b); } ll get_lcm(ll a, ll b) { return a / get_gcd(a, b) * b; }

ll gcdExtended(ll a, ll b, ll *x, ll *y) { if (a == 0) { *x = 0; *y = 1; return b; } ll x1, y1; ll gcd = gcdExtended(b%a, a, &x1, &y1); *x = y1 - (b/a) * x1; *y = x1; return gcd; }