#define I __int128
void exgcd(I a,I&x,I b,I&y,I c){
if(b==0) x=c/a,y=0;
else exgcd(b,y,a%b,x,c),y-=a/b*x;
}
inline bool merge(I x1,I p1,I x2,I p2,I&x,I&p){
I a,b,d=__gcd(p1,p2);
if((x2-x1)%d!=0) return false;
exgcd(p1,a,p2,b,x2-x1);
p=p1/d*p2;
x=((a*p1+x1)%p+p)%p;
return true;
}