import java.util.Scanner;

public class ChineseRemainderTheorem {

    static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    static long modInverse(long a, long m) {
        a = Math.floorMod(a, m);

        for (long x = 1; x < m; x++) {
            if ((a * x) % m == 1) {
                return x;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print(
                "Enter remainders (space-separated, e.g., 2 3 2): ");
        String[] rInput = sc.nextLine().trim().split("\\s+");

        System.out.print(
                "Enter moduli (space-separated, e.g., 3 5 7): ");
        String[] mInput = sc.nextLine().trim().split("\\s+");

        if (rInput.length != mInput.length) {
            System.out.println(
                    "Error: Remainders and moduli must have equal length.");
            sc.close();
            return;
        }

        int n = rInput.length;
        long[] r = new long[n];
        long[] m = new long[n];

        long product = 1;

        for (int i = 0; i < n; i++) {
            r[i] = Long.parseLong(rInput[i]);
            m[i] = Long.parseLong(mInput[i]);

            if (m[i] <= 1 || product > Long.MAX_VALUE / m[i]) {
                System.out.println("Invalid moduli or product too large.");
                sc.close();
                return;
            }

            product *= m[i];
        }

        // CRT requires pairwise-coprime moduli.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (gcd(m[i], m[j]) != 1) {
                    System.out.println(
                            "Error: Moduli must be pairwise coprime.");
                    sc.close();
                    return;
                }
            }
        }

        long result = 0;

        for (int i = 0; i < n; i++) {
            long Mi = product / m[i];
            long inverse = modInverse(Mi % m[i], m[i]);

            if (inverse == -1) {
                System.out.println("Modular inverse does not exist.");
                sc.close();
                return;
            }

            long term = Math.floorMod(r[i], m[i]);
            term = (term * (Mi % product)) % product;
            term = (term * inverse) % product;

            result = (result + term) % product;
        }

        System.out.println("CRT Solution = " + result);

        sc.close();
    }
}