2019牛客暑期多校训练营（第十场） D

def Ex_Euclid(a, b):
    if 0 == b:
        x = 1
        y = 0
        q = a
        return x, y, q
    xyq = Ex_Euclid(b, a % b)
    x = xyq[0]
    y = xyq[1]
    q = xyq[2]
    temp = x
    x = y
    y = temp-a//b*y
    return x, y, q
 
 
def inv(a, b):
    return Ex_Euclid(a, b)[0]
 
 
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)
 
 
def merge(a1, b1, a2, b2):
    d = gcd(b1, b2)
    c = a2-a1
    if c % d:
        return (0, 0, -1)
    c = (c % b2+b2) % b2
    c = int(c/d)
    b1 = int(b1/d)
    b2 = int(b2/d)
    c = c*inv(b1, b2)
    c=c%b2
    c=c*(b1*d)
    c=c+a1
    b3=b1*b2*d
    a3=(c%b3+b3)%b3
    return (a3,b3,1)
 
 
def CRT(a_list, b_list, n):
    a1 = a_list[0]
    b1 = b_list[0]
    for i in range(n-1):
        a2 = a_list[i+1]
        b2 = b_list[i+1]
        (aa, bb, flag) = merge(a1, b1, a2, b2)
        if flag==-1:
            return -1
        a1=aa
        b1=bb
    return (a1%b1+b1)%b1
 
 
def main():
    n, m = map(int, input().strip().split())
    a_list = []
    b_list = []
    for i in range(n):
        x, y = map(int, input().strip().split())
        a_list.append(x)
        b_list.append(y)
    ans = CRT(b_list, a_list, n)
    if ans==-1:
        print("he was definitely lying")
    elif ans>m:
        print("he was probably lying")
    else:
        print(ans)
 
if __name__ == '__main__':
    main()