CRT

ll crt() {
    ll n, N = 1;
    cin >> n;
    for (ll i = 0; i < n; i++) {
        cin >> p[i] >> r[i];
        N *= p[i];
        // L equiv r[i] (mod p[i])
    }
    bool fucked = false;
    for (ll i = 0; i < n; i++)
        for (ll j = i + 1; j < n; j++)
            if (gcd (p[i], p[j]) != 1) fucked = true;
    if (fucked) return -1;
    ll L = 0;
    for (ll i = 0; i < n; i++) {
        ll y = N / p[i];
        ll X, Y;
        ll g = e_gcd (y, p[i], X, Y);
        L += (r[i] * y * X) % N;
        L %= N;
    }
    return (L + N) % N;
}