write a program in cpp with such algorithm. thank you!

1) Write an extended Euclidean algorithm to express gcd(a,b) as a linear combination with integer coefficients of the integers a and b. This function accepts two integers as arguments. It returns a list whose first element is the greatest common divisor of the arguments and whose second element is a sublist whose members are the Bzout coefficients. The extended Euclidean algorithm can be used to express gcd(a,b) as a linear combination with integer coefficients of the integers a and b. We set s0=1,s1=0, to =0, and t1=1 and let sj=sj2qj1sj1 and tj=tj2qj1tj1 for j=2,3,,n, where the qj are the quotients in the divisions used when the Euclidean algorithm finds gcd(a,b), as shown in the text. It can be shown that gcd(a,b)=Sna+tnb. The main advantage of the extended Euclidean algorithm is that it uses one pass through the steps of the Euclidean algorithm to find Bzout coefficients of a and b, unlike the method in the text which uses two passes. Use the extended Euclidean algorithm to express gcd(252,356) as a linear combination of 252 and 356. Use the extended Euclidean algorithm to express gcd(144,89) as a linear combination of 144 and 89. Use the extended Euclidean algorithm to express gcd(1001, 100001) as a linear combination of 1001 and 100001