long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
// Finds such x and y, that a * x + b * y = gcd(a, b)
long long extended_gcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long x1, y1;
long long g = extended_gcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// Solves equation a * x + b * y = c, writes answer to x and y
void solveDiophantine(long long a, long long b, long long c, long long &x, long long &y) {
long long g = extended_gcd(a, b, x, y);
if (c % g != 0) {
puts("Impossible");
exit(0);
}
c /= g;
x = x * c; y = y * c;
}