from functools import reduce


def CRT_calculator(A_list, N_list) -> int:
    """Solve the simultaneous congruences using Chinese Remainder Theorem (CRT)

    x = a_1 mod (n_1)
    x = a_2 mod (n_2)
    ...
    x = a_k mod (n_k)

    Args:
        A_list (list[int]): List of a_i from 1 to k
        N_list (list[int]): List of n_i from 1 to k

    Note:
        List arguments need to have same length, and every number in N_list need to be co-prime
        to each other.

    Returns:
        int: Smallest positive integer x such that it satisfies all congruences.
    """

    def get_inverse(c, n):
        r = c % n

        if r == 1 or r == n - 1:
            return r

        for i in range(2, n - 1):
            if (c * i) % n == 1:
                return i

        raise ArithmeticError("No solution!")

    n = reduce(lambda x, y: x * y, N_list)

    C_list = [n // ni for ni in N_list]

    D_list = [get_inverse(ci, ni) for ci, ni in zip(C_list, N_list)]

    result = (
        reduce(
            lambda x, y: x + y, [a * c * d for a, c, d in zip(A_list, C_list, D_list)]
        )
        % n
    )

    return result