#include using namespace std; int modinv(int a,int m){ a%=m; if((a-1)%m==0)return a; return(1-(long)m*modinv(m,a))/a; } paircrt_mod(vectorr,vectorm,int mod){ int n=r.size(); assert(m.size()==n); unordered_map>qr; for(int i=0;iQ)swap(q,Q),swap(a,R); if((R-a)%q)return{0,0}; } if(x>1){ int a=r[i]%x; if(!qr.count(x))qr[x]={x,a}; else if((qr[x].second-a)%x)return{0,0}; } } m.clear(),r.clear(); for(auto[p,qr]:qr)m.push_back(qr.first),r.push_back(qr.second); n=m.size(); m.push_back(mod); vectorx(n+1),p(n+1,1); for(int i=0;i>n; vectorr(n),m(n); for(int i=0;i>r[i]>>m[i]; auto[x,l]=crt_mod(r,m,1000000007); if(l==0){cout<<-1<<'\n';return 0;} bool zero=1; for(int i=0;i0)zero=0; cout<<(zero?l:x)<<'\n'; }