Chinese Remainder Theorem

struct ChineseRemainder 
{
    
    vector<ll> a;
    vector<ll> mods;
    // find x congruence a[i] (mod mods[i])
    
    void init(vector<ll> a_, vector<ll> mods_) {
        a = a_;
        mods = mods_;
    }
    
    ll normalize(ll x, ll m) {
        if (x >= 0 && x < m)
            return x;
        x = ((x % m) + m) % m;
        return x;
    }
    
    pair<ll, ll> findX() {
        ll ans = normalize(a[0], mods[0]);
        ll lcm = mods[0];
        for(int i = 1; i < a.size(); ++i) {
            ll ai = normalize(a[i], mods[i]);
            
            ll d, x, y;
            d = gcdExtended(lcm, mods[i], x, y);

            if((ai - ans) % d != 0) {
                return make_pair(0, 0);
            }
            
            ans = normalize(ans + x * (ai - ans) / d % (mods[i] / d) * lcm, lcm * mods[i] / d);
            lcm = get_lcm(lcm, mods[i]); 
        }
        
        return make_pair(ans, lcm);
    }
};