#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <stdlib.h>

using namespace std;

#define N 10100

/*对于x=r0(mod m0)

     x=r1(mod m1)

        ...

     x=rn(mod mn)

输入数组m和数组r，返回[0,[m0,m1,...,mn]-1] 范围内满足以上等式的x0。

x的所有解为:x0+z*[m0,m1,...mn](z为整数)

*/

long long cal_axb(long long a,long long b,long long mod)

{

    //防乘法溢出

    long long sum=;

    while(b)

    {

        if(b&) sum=(sum+a)%mod;

        b>>=;

        a=(a+a)%mod;

    }

    return sum;

}

//ax + by = gcd(a,b)

//传入固定值a,b.放回 d=gcd(a,b), x , y

void extendgcd(long long a,long long b,long long &d,long long &x,long long &y)

{

    if(b==){d=a;x=;y=;return;}

    extendgcd(b,a%b,d,y,x);

    y -= x*(a/b);

}

long long Multi_ModX(long long m[],long long r[],int n)

{

    long long m0,r0;

    m0=m[]; r0=r[];

    for(int i=;i<n;i++)

    {

        long long m1=m[i],r1=r[i];

        long long k0,k1;

        long long tmpd;

        extendgcd(m0,m1,tmpd,k0,k1);

        if( (r1 - r0)%tmpd!= ) return -;

        k0 *= (r1-r0)/tmpd;

        m1 *= m0/tmpd;

        r0 = ( cal_axb(k0,m0,m1)+r0)%m1;

        m0=m1;

    }

    return (r0%m0+m0)%m0;

}

/*

int main()

{

    int k;

    while(cin>>k)

    {

        long long a[N],r[N];

        for(int i=0;i<k;i++)

            cin>>a[i]>>r[i];

        cout<<Multi_ModX(a,r,k)<<endl;

    }

    return 0;

}

*/