Write a function `extended_gcd(a: int, b: int) -> tuple` that takes two integers `a` and `b` and returns a tuple `(g, x, y)` where `g = gcd(a, b)` and `x, y` are integers satisfying `a * x + b * y = g`. The gcd must always be non-negative: `gcd(0, 0) = 0`, `gcd(a, 0) = |a|`, `gcd(0, b) = |b|`. The returned coefficients must come from the standard extended Euclidean recursion applied to the *absolute values* of the inputs, and then the signs must be adjusted so that the final equation `a*x + b*y = g` holds exactly. In particular, for positive inputs the coefficients must match the standard recursive output (e.g., `extended_gcd(30, 12) == (6, 1, -2)`). For negative inputs, the coefficients must be the same as those for the absolute values, with signs flipped for any negative input: for example, `extended_gcd(-30, 12)` must return `(6, -1, -2)` because `(-30)*(-1) + 12*(-2) = 6`, and `extended_gcd(30, -12)` must return `(6, 1, 2)` because `30*1 + (-12)*2 = 6`. The function must handle arbitrary integers (including zero and negative values) without any exceptions.
Constraints
- `-10^18 <= a, b <= 10^18` (fits in 64-bit integers).
- Time complexity: O(log(min(|a|, |b|))) expected.
- Space complexity: O(1) or O(log n) for recursion.