``````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
ans =(a1 % b1+b1) % b1
return ans
# def CRT(m_list,r_list,n):
#     M=m_list[0], R=r_list[0]
#     for i in range(n):
#         d=Ex_Euclid(M,m_list[i+1])[0]
#         if (r_list[i+1]-R)%d:
#             return -1
#         x = (r[i] - R) / d * x % (m[i] / d)
#         R += x * M
#         M = M / d * m[i]
#         R %= M
#     if R>0:
#         return R
#     else:
#         return R+M
def main():
#n=int(input())
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(int(ans))

if __name__ == '__main__':
main()
``````