[Kattis] Chinese Remainder Theorem (non-relatively prime moduli)

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Chinese Remainder Theorem (non-relatively prime moduli)
Source            : Kattis
Category          : Number Theory
Algorithm         : Chinese Remainder Theorem (Non Coprime)
Verdict           : Accepted

import math
 
def read():
    return map(int, input().split())
 
def extended_euclid_algorithm(a, b):
    if b is 0:
        return (1, 0, a)
    else:
        x, y, d = extended_euclid_algorithm(b, a%b)
        x1 = y
        y1 = x - (a // b) * y
        x = x1
        y = y1
        return (x, y, d)
 
def chinese_remainder_theorem(A, M):
    if len(A) is not len(M):
        return -1, -1
    a1 = A[0]
    m1 = M[0]
    a2 = A[1]
    m2 = M[1]
    g = math.gcd(m1, m2)
    if a1 % g != a2 % g:
        return -1, -1
    p, q, d = extended_euclid_algorithm(m1 // g, m2 // g)
    mod = m1 // g * m2
    x = (a1 * (m2//g) * q  + a2 * (m1//g) * p) % mod
    a1 = x
    if a1 < 0:
        a1 += mod
    m1 = mod
    return a1, m1
 
def solve():
    tc = int(input())
    for tcase in range (tc):
        a, n, b, m = read()
        A = []
        M = []
        A.append(a)
        A.append(b)
        M.append(n)
        M.append(m)
        x, k = chinese_remainder_theorem(A, M)
        if x is -1:
            print("no solution")
        else:
            print("{} {}".format(x, k))
        A.clear()
        M.clear()
    return
 
solve()