def gcd_ext(a, b): ''' 1次不定方程式 ax+by=gcd(a, b) の解と最大公約数を返す。負の値には未対応 x, y, gcd(a, b) ''' if a < b: x, y, s = gcd_ext(b, a) return y, x, s s, xs, ys = a, 1, 0 t, xt, yt = b, 0, 1 while t > 0: n = s // t s, t = t, s % t xs, xt = xt, xs - n * xt ys, yt = yt, ys - n * yt return xs, ys, s def crt(b, m): ''' すべてのiについて x≡b[i](mod, m[i]) の論理積を満たす x と lcm(m[:]) を求める。 解がない場合 -1, 0 を返す ''' n = len(b) assert n == len(m) m0, b0 = 1, 0 for i in range(n): m1, b1 = m[i], b[i] % m[i] p, _, d = gcd_ext(m0, m1) # m0 * p + m1 * q = gcd(m0, m1) if (b1 - b0) % d: # b0 ≡ b1 (mod gcd(m0, m1)) の不成立 return -1, 0 lcm = m0 * m1 // d b0 = (b0 + (b1 - b0) // d * p * m0) % lcm m0 = lcm return b0, lcm import sys xy = list(map(int, sys.stdin.read().split())) x = xy[0::2] y = xy[1::2] ans, lcm = crt(x, y) print(ans if ans else lcm)