Given four integers A, B, X0 and Y0 such that gcd(A, B) = 1 and A × X0 + B × Y0 = 1. Find another pair of integers X’ and Y’, where X’ ≠ X0, Y’ ≠ Y0, |X’|, |Y’| ≤ 109 and A × X’ + B × Y’ = 1.
The pair X0, Y0 is selected by the following algorithm:
pair< int, int > extended_euclidean(int a, int b) {
if (b == 0)
return make_pair(1, 0);
else {
pair< int, int > t = extended_euclidean(b, a % b);
return make_pair(t.second, t.first – a / b * t.second);
}
}
However, that is another pair of shoes and the intended solution does not depend on how the pair is chosen.
Each test case consists of four space-separated integers A, B, X0 and Y0 (A, B, |X0|, |Y0| ≤ 108, gcd(A, B) = 1, A ≠ 0, B ≠ 0) in a line. The input is terminated by A = B = X0 = Y0 = 0.
For each test case, output two integers X’ and Y’ (|X’|, |Y’| ≤ 109) separated by a space character. If there are more than one pairs that meet the requirement, you may output any one of them.