The Congruence Solver: Solve ax Ôëí b (mod n)

In the Hall of Equations, the Royal Algebraist presents a linear congruence: ax Ôëí b (mod n). This equation has solutions if and only if gcd(a, n) divides b. When solutions exist, there are exactly gcd(a, n) distinct solutions modulo n. "The linear congruence is the gateway to modular problem-solving," the Algebraist says. "Find gcd(a, n). If it divides b, use the Extended Euclidean Algorithm to find one solution, then generate all distinct solutions." Given integers a, b, and n, find the smallest non-negative solution x to ax Ôëí b (mod n). If no solution exists, output -1. Constraints: 1 <= a, n <= 10^9, 0 <= b <= 10^9 Input: 2 3 5 Output: 4 Input: 4 2 6 Output: 2