## Algorithm

From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX + BY = D, where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding X, Y and D. Input The input will consist of a set of lines with the integer numbers A and B, separated with space (A, B < 1000000001). Output For each input line the output line should consist of three integers X, Y and D, separated with space. If there are several such X and Y , you should output that pair for which |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria,

output the pair for which X ≤ Y .

Sample Input 4 6 17 17

Sample Output -1 1 2 0 1 17

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

`````` #include <bits/stdc++.h>
using namespace std;

int x,y,d;

// ax + by = d
// store x, y, and d as global variables
void extendedEuclid(int a, int b) {
if (b == 0) { x = 1; y = 0; d = a; return; } // base case
extendedEuclid(b, a % b); // similar as the original gcd
int x1 = y;
int y1 = x - (a / b) * y;
x = x1;
y = y1;
}

int main() {
int a,b;
while(scanf("%d %d",&a,&b) != EOF) {
extendedEuclid(a,b);
printf("%d %d %d\n",x,y,d);
}
}``````
Copy The Code &

Input

cmd
4 6
17 17

Output

cmd
-1 1 2
0 1 17