int crt(int a1, int m1, int a2, int m2){
    // x = a1 (mod m1)
    // x = a2 (mod m2)
    a1 *= m2;
    a2 *= m1;
    // m2 x = a1 m2 (mod m1 m2)
    // m1 x = a2 m1 (mod m2 m1)
    int m = m1 * m2;
    int b1 = m2, b2 = m1;
    // b1 x = a1 (mod m)
    // b2 x = a2 (mod m)
    while (b2){
          int t = b1 / b2;
          b1 -= t * b2;
          a1 -= t * a2;
          a1 %= m;
          if (a1 < 0) a1 += m;
          swap(b1, b2);
          swap(a1, a2);
    }
    return a1;
}