Harryxun/stf_run huggingface dataset:
from math import gcd

def cR(A, i):
    if i == len(A):
        return 0
    else:
        g = 0
        for i in range(i, len(A)):
            g = gcd(g, A[i])
        return g

def cL(A, i):
    if i == 1:
        return 0
    else:
        g = 0
        for i in range(i+1):
            g = gcd(g, A[i])
        return g


n = int(input())
A = list(map(int, input().split()))
A.append(0)
R = [0] * (n+2)
L = [0] * (n+2)
M = [0] * (n+2)

g = A[n-1]
for i in range(n-1, -1, -1):
    R[i] = gcd(g, A[i])

g = A[0]
for i in range(1,n+1):
    L[i] = gcd(g, A[i-1])

for i in range(n):
    M[i] = gcd(L[i], R[i+1])

# print(L, R, M)
print(max(M))

### FIXED CODE ###

# from math import gcd

def gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 

n = int(input())
A = list(map(int, input().split()))

R = [0] + list(A) + [0]
L = [0] + list(A) + [0]
M = [0] * (n+2)


for i in range(n, 0, -1):
    R[i] = gcd(R[i], R[i+1])


for i in range(1,n+1):
    L[i] = gcd(L[i], L[i-1])

for i in range(1,n+1):
    M[i] = gcd(L[i-1], R[i+1])

# print("A   ", A, " ")
# print("L", L)
# print("R", R)
# print("M", M)
print(max(M))
def main():
    s = input()
    k = int(input())
    ss = set()
    if len(s) <= 5:
        for i in range(len(s)):
            for j in range(i+1, len(s)+1):
                ss |= {s[i:j]}
    else:
        m = sorted(s)[0]
        for i in range(len(s)):
            if s[i] == m:
                for j in range(i+1, len(s)+1):
                    ss |= {s[i:j]}
    print(sorted(ss)[k-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
if n == 1:
    print(s)
elif n == 2:
    l2 = sorted(list(set([s[i:i+2] for i in range(n-1)])))
    print(l2[0])
elif n == 3:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    out = sorted(l1 + l2 + l3)
    print(out[k-1])
elif n == 4:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    out = sorted(l1 + l2 + l3 + l4)
    print(out[k-1])
else:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    l5 = list(set([s[i:i+5] for i in range(n-4)]))
    out = sorted(l1 + l2 + l3 + l4 + l5)
    print(out[k-1])
n = int(input())
h = list(map(int, input().split()))
dp = [0 for _ in range(n)]

def f(cur, prev1, prev2, dp):
    if len(dp) == cur:
        return
    prev1_cost = 100000000 if prev1 < 0 else dp[prev1] + abs(h[cur] - h[prev1])
    prev2_cost = 100000000 if prev2 < 0 else dp[prev2] + abs(h[cur] - h[prev2])
    dp[cur] = prev1_cost if prev1_cost < prev2_cost else prev2_cost
    f(cur + 1, prev1 + 1, prev2 + 1, dp)

f(1, 0, -1, dp)
print(dp[-1])

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
dp = [float('INF') for _ in range(n)]
for i in range(n):
    if 0 == i:
        dp[i] = 0
    elif 1 == i:
        dp[i] = abs(h[i-1] - h[i])
    else:
        dp[i] = min(dp[i-1] + abs(h[i-1] - h[i]),
                    dp[i-2] + abs(h[i-2] - h[i]))
print(dp[-1])
S = input()
a = S[0]
b = S[1]
c = S[2]
d = S[3]
l = []
l.append(a)
l.append(b)
l.append(c)
l.append(d)
k = list(set(l))
if len(k) == 2:
  if count(a) == 2:
    print("Yes")
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

S = input()
a = S[0]
b = S[1]
c = S[2]
d = S[3]
l = []
l.append(a)
l.append(b)
l.append(c)
l.append(d)
k = list(set(l))
if len(k) == 2:
  if l.count(a) == 2:
    print("Yes")
  else:
    print("No")
else:
  print("No")
def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    l=[0]*(10**5)
    for i in a:
        l[i]+=1
    ans=sum(a)
    q=int(input())
    for i in range(q):
        b,c=map(int,input().split())
        x=l[b]
        ans+=(c-b)*x
        l[c]+=x
        l[b]=0
        print(ans)


if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    n=int(input())
    a=list(map(int,input().split()))
    l=[0]*(10**5+1)
    for i in a:
        l[i]+=1
    ans=sum(a)
    q=int(input())
    for i in range(q):
        b,c=map(int,input().split())
        x=l[b]
        ans+=(c-b)*x
        l[c]+=x
        l[b]=0
        print(ans)

if __name__ == '__main__':
    resolve()
import numpy as np

A = input()
B = input()

N,X = map(int,A.split())
L = np.array(list(map(int,B.split( ))))
L_sum = 0
jump = 1
for i in range(N+1):
  L_sum += L[i]
  if(L_sum<X):
    jump += 1 
  else:
    jump += 0

print(jump)

### FIXED CODE ###

import numpy as np

A = input()
B = input()

N,X = map(int,A.split())
L = np.array(list(map(int, B.strip().split())))

L_sum = 0
jump = 1

for i in range(N):
  L_sum += L[i]
  if(L_sum>X):
    jump += 0
  else:
    jump += 1

print(jump)
def check(S) :
    mae = int(S[:2])
    ato = int(S[2:])
    if mae == 0 :
        return "NA"
    if ato == 0 :
        return "NA"
    if mae > 12 and ato > 12 :
        return "NA"
    if mae < 13 and ato < 13 :
        return "AMBIGUOUS"
    
    if mae < 13 :
        return "MMYY"
    if mae > 12
        return "YYMM"


S = input()
print(check(S))


### FIXED CODE ###

def check(S) :
    mae = int(S[:2])
    ato = int(S[2:])
    
    if mae == 0 and ato <= 12 and ato > 0 :
        return "YYMM"
    if ato == 0 and mae <= 12 and mae > 0 :
        return "MMYY"
    
    if mae == 0 or ato == 0 :
        return "NA"
    if mae > 12 and ato > 12 :
        return "NA"
    if mae <= 12 and ato <= 12 :
        return "AMBIGUOUS"
    if mae > 12 :
        return "YYMM"

    return "MMYY"
    
    

S = input()
print(check(S))
from heapq import heappush, heappop

INF =  10000000000

def dijkstra(r, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dp = []
line = input()
n = int(line)
edge = {}
for _ in range(0, n - 1):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in edge:
        edge[s] = [[t, d]]
    else:
        edge[s] += [[t, d]]
    if t not in edge:
        edge[t] = [[s, d]]
    else:
        edge[t] += [[s, d]]
dp = dijkstra(0, n, edge)
i = [j for j, x in enumerate(dp) if x == max(dp)]
dp = dijkstra(i[0], n, edge)
diam = max(dp[i] if dp[i] != INF else 0 for i in range(0, n))
print(diam)


### FIXED CODE ###

def solve(prev, r, dic):
    d = 0
    t = r
    stack = []
    stack += [[prev, r, d]]
    while stack:
        prev, r, d1 = stack.pop(-1)
        if r in dic:
            for vtx, cost in dic[r]:
                if vtx == prev:
                    continue
                stack += [[r, vtx, d1 + cost]]
                if d < d1 + cost:
                    d = d1 + cost
                    t = vtx
    return d, t

line = input()
n = int(line)
edge = {}
for _ in range(0, n - 1):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in edge:
        edge[s] = [[t, d]]
    else:
        edge[s] += [[t, d]]
    if t not in edge:
        edge[t] = [[s, d]]
    else:
        edge[t] += [[s, d]]
r1, t1 = solve(-1, 0, edge)
r2, t2 = solve(-1, t1, edge)
print(r2)
w,h,x,y,r = map(int,raw_input().split())
if r =< x <= w - r and r =< y <= h - r:
  print ("Yes")
else
  print ("No")  

### FIXED CODE ###

w,h,x,y,r = map(int,raw_input().split())
if r <= x <= w - r and r <= y <= h - r:
  print ("Yes")
else:
  print ("No")
import sys
import numpy as np


def main(N, S, dp):
    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
        ans = max(ans, max(dp[i]))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE' and 0:
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc.export('main', 'i8(i8,i8[:],i8[:,:])')
    cc.compile()

from my_module import main

N = int(input())
S = np.array([ord(_) for _ in input()])
dp = np.zeros((N + 1, N + 1), dtype=int)
print(main(N, S, dp))


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
def insertionSort(A, n, g):
    cnti = 0
    for i in range(g, n):
        v = A[i]
        j = i-g
        while (j >= 0 and A[j] > v):
            A[j + g] = A[j]
            j -= g
            cnti += 1
        A[j+g] = v
    return cnti
def shellSort(A,n):
    cnt = 0
    G = []
    for k in range(int((n/3)) +1):
        h = 3*k + 1
        if (h <= n and len(G) < 100):
            G.append(h)
        elif(len(G) == 100):
            break    
    G.reverse()
    m = len(G)
    for i in range(m):
        cnt += insertionSort(A, n, G[i])
    print(m)
    for i in range(m):
        if (i == m-1):
            print('{}'.format(G[i]), end = '')
        else:
            print('{}'.format(G[i]), end = ' ')
    return cnt
        
        
        
n = int(input())
nlist = []
for i in range(n):
    x = int(input())
    nlist.append(x)
    
c = shellSort(nlist,n)
print()
print(c)
for i in nlist:
    print(i)


### FIXED CODE ###

def insertionSort(A, n, g):
    cnti = 0
    for i in range(g, n):
        v = A[i]
        j = i-g
        while (j >= 0 and A[j] > v):
            A[j + g] = A[j]
            j -= g
            cnti += 1
        A[j+g] = v
    return cnti
def shellSort(A,n):
    cnt = 0
    G = [1]
    h = 1
    for k in range(int(n**0.33333333)+1):
        h = 3*h + 1  ## h=1,4,13,40,121,364 ... 왜 이게 효율이 좋은지는 모르겠음(다른 사이트 봄)
        if (h <= n and len(G) < 100):
            G.append(h)
        elif(len(G) == 100):
            break    
    G.reverse()
    m = len(G)
    for i in range(m):
        cnt += insertionSort(A, n, G[i])
    print(m)
    for i in range(m):
        if (i == m-1):
            print('{}'.format(G[i]), end = '')
        else:
            print('{}'.format(G[i]), end = ' ')
    return cnt
        
        
        
n = int(input())
nlist = []
for i in range(n):
    x = int(input())
    nlist.append(x)
    
c = shellSort(nlist,n)
print()
print(c)
for i in nlist:
    print(i)
N, A, B, C, D = list(map(int, input().split()))

S = input()

# 以下indexに変更
A-=1
B-=1
C-=1
D-=1

L = [1]*N

# 0を岩、1を通路とする
for i in range(N):
    if S[i] == '#':
        L[i] =  0


def search(idx, g, reversed_goal):
    L[idx] =0
    if not reversed_goal:
        if idx+1 == g:
            L[idx] = 1
            L[g] = 0
            return True
        if idx+2 == g: 
            L[idx] = 1
            L[g] = 0
            return True

    else:
        if idx+2 == g and L[idx+1] and L[idx+3]:
            L[g] = 0
            return True

        if idx+1 == g and L[idx+2]:
            L[g] = 0
            return True

        if L[idx+1] == g or L[idx+2] == g:
            return False


    if reversed_goal and [idx+2] and L[idx+1]:
        L[idx] =1
        L[idx+1] = 0
        return True


    if idx+2 <= g and L[idx+2]:
        L[idx] = 1
        return search(idx+2, g, reversed_goal)
    
    if idx+1 <= g and L[idx+1]:
        L[idx] = 1
        return search(idx+1, g, reversed_goal)
    
    return False

def main():
    reversed_goal = C > D
    if not reversed_goal:
        if search(B,D,False):
            if search(A,C,False):
                return 'Yes'
            
        return 'No'

    else:
        if search(B,D,True):
            if search(A,C,False):
                return 'Yes'

        return 'No'

ans = main()
print(ans)

### FIXED CODE ###

if __name__ == '__main__':
    N, A, B, C, D = map(int, input().split())
    S = str(input())
 
    answer = "-1"
 
    if C < D:
       if S[A:D:].count("##") >= 1:
           answer = "No"
       else:
           answer = "Yes"
    else:
       if S[B-2:D+1:].count("...") >= 1:
           answer = "Yes"
       else:
           answer = "No"
 
    print(answer)
N = input()
check = 0
for i in N:
  check += i
if check % 9 == 0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

N = input()
check = 0

for i in N:
    check += int(i)

if check % 9 == 0:
    print("Yes")
else:
    print("No")
s=list(str(input()))
t=list(str(input()))
s.sort()
t.sort()
#print(s,t)

for i in range(min(len(s),len(t))):
    if s[i]<t[i]:
        print("Yes")
        exit()
    elif s[i]>t[i]:
        print("No")
        exit()
if len(s)<t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=list(str(input()))
t=list(str(input()))
s.sort()

t.sort(reverse=True)
#print(s,t)

for i in range(min(len(s),len(t))):
   # print(s[i],t[i])
    if s[i]<t[i]:
        print("Yes")
        exit()
    elif s[i]>t[i]:
        print("No")
        exit()
if len(s)<len(t):
    print("Yes")
else:
    print("No")
s = input()

cnt = 0
q = []
now = 0

for i in range(len(s)):
    if s[i] == 'A' or s[i] == 'T' or s[i] == 'C' or s[i] == 'G':
        cnt += 1
    else:
        q.append(cnt)
        cnt = 0

print(max(q))


### FIXED CODE ###

s = input()
ans = 0
for i in range(len(s)):
    for j in range(i, len(s)):
        if all('ACGT'.count(c) == 1 for c in s[i:j+1]):
            ans = max(ans, j-i+1)

print(ans)
contest = input()

if contest = "ABC":
  print("ARC")
else:
  print("ABC")
  

### FIXED CODE ###

contest = input()

if contest == "ABC":
  print("ARC")
else:
  print("ABC")
a = int(input())
a -= a%5
print(2*a - a%500)

### FIXED CODE ###

s = input()
if s[2] == s[3] and s[4] == s[5]:
    print("Yes")
else:
    print("No")
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
n=int(input())
ans=[[0,0,0] for i in range(3)]
count=-1
for i in range(n):
  s=int(input())
  for T in [A,B,C]:
    count+=1
    if s in T:
      ans[count][T.index(s)]=1
for i in range(3):
  if ans[i]==[1,1,1]:
    print("Yes")
    exit()
for i in range(3):
  if [ans[i][j] for j in range(3)]==[1,1,1]:
    print("Yes")
    exit()
if [ans[0][0],ans[1][1],ans[2][2]]==[1,1,1]:
  print("Yes")
  exit()
if [ans[0][2],ans[1][1],ans[2][0]]==[1,1,1]:
  print("Yes")
  exit()
print("No")


### FIXED CODE ###

A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
n=int(input())
ans=[[0,0,0] for i in range(3)]

for i in range(n):
  s=int(input())
  count=-1
  for T in [A,B,C]:
    count+=1
    if s in T:
      
      ans[count][T.index(s)]=1
for i in range(3):
  if ans[i]==[1,1,1]:
    print("Yes")
    exit()
for i in range(3):
  if [ans[j][i] for j in range(3)]==[1,1,1]:
    print("Yes")
    exit()
if [ans[0][0],ans[1][1],ans[2][2]]==[1,1,1]:
  print("Yes")
  exit()
if [ans[0][2],ans[1][1],ans[2][0]]==[1,1,1]:
  print("Yes")
  exit()
print("No")
import statistics
def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	seq = []
	for i in range(1, n+1):
		seq.append(abs(i-a[i-1]))
	seq = sorted(seq)
	m = statistics.median(seq)
	ans = 0
	for i in seq:
		ans += abs(i-m)
	print(ans)
resolve()

### FIXED CODE ###

import statistics
def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	seq = []
	for i in range(1, n+1):
		seq.append(i-a[i-1])
	seq = sorted(seq)
	m = int(statistics.median(seq))
	ans = 0
	for i in seq:
		ans += abs(i-m)
	print(ans)
resolve()
# 後ろから順に考える
# 最後のA_Kは必ず2である必要がある
# A_Kの前には2~3人である必要がある
# ...

K = int(input())
As = list(map(int, input().split()))
As.reverse()

fail = False
if As[0] != 2:
    fail = True
else:
    mn = 2
    mx = 3
    for a in As[1:]:
        # 今 [mn, mx] = [4, 13], a = 3だとする
        # a人組をつくったあとにありうる数は3の倍数なので、ここでは6, 9, 12のみありうる
        if mn % a != 0:
            mn = (mn // a) * a + a
        if mx % a != 0:
            mx = (mx // a) * a
        if mn > mx:
            fail = True
            break

        # mxを修正
        mx = mx + (a - 1)
if fail:
    print(-1)
else:

### FIXED CODE ###

# 後ろから順に考える
# 最後のA_Kは必ず2である必要がある
# A_Kの前には2~3人である必要がある
# ...

K = int(input())
As = list(map(int, input().split()))
As.reverse()

fail = False
if As[0] != 2:
    fail = True
else:
    mn = 2
    mx = 3
    for a in As[1:]:
        # 今 [mn, mx] = [4, 13], a = 3だとする
        # a人組をつくったあとにありうる数は3の倍数なので、ここでは6, 9, 12のみありうる
        if mn % a != 0:
            mn = (mn // a) * a + a
        if mx % a != 0:
            mx = (mx // a) * a
        if mn > mx:
            fail = True
            break

        # mxを修正
        mx = mx + (a - 1)
if fail:
    print(-1)
else:
    print(mn, mx)
#普通にやるとTLE
n = int(input())

a = list(map(int, input().split()))

total = sum(a)
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)

### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))

total = sum(a)
x = 0
ans = float("inf")
for i in range(n-1):
  x += a[i]
  y = total - x
  if(abs(x-y) < ans):
    ans = abs(x-y)
    
print(ans)
A,B,C=X,Y,Z=map(int,input().split())

A = Y
B = X
A = Z
C = X

print(str(A)+' '+str(B)+' '+str(C))

### FIXED CODE ###

X,Y,Z=map(int,input().split())
A,B,C=X,Y,Z
 
A = Y
B = X
A = Z
C = Y
 
print(str(A)+' '+str(B)+' '+str(C))
import sys
from math import factorial
#nCi
def com(n, i):
    return int(factorial(n)/factorial(i)/factorial(n-i))
    
def cal1(num):
    total = 1
    if num < 1: return total
    if num == 1: return 2
    large_num = num
    for small_num in range(1, num):
        if small_num > large_num: break
        total += com(large_num, small_num)
        large_num -= 1
    return total

def main():
    N, M = map(int, input().split())
    len_list = []
    pre_a = -1
    for m in range(M):
        a = int(input())
        if (pre_a + 1) == a: sys.exit("0")
        len_list.append(a-(pre_a+3))
        pre_a = a
    len_list.append(N-(pre_a+2))
    ans = 1
    for num in len_list:
        ans *= cal1(num)
    print(ans%1000000007)
    
main()

### FIXED CODE ###

def run():
  N, M = map(int, input().split())
  stairs = [1] * (N+1)
  for m in range(M):
    a = int(input())
    stairs[a] = 0
  #print(stairs)
  for n in range(2, N+1):
    stairs[n] = (stairs[n-1] + stairs[n-2])*stairs[n]
  print(stairs[N]%1000000007)
  
if __name__ == '__main__':
  run()
a,b,c=map(int,input().split())
print(sum(a,b,c))

### FIXED CODE ###

l=[int(i) for i in input()]
print(sum(l))
N = int(input())
A = [int(a) for a in input().split()]
B = deque([])
for n in range(N):
    if n % 2 == 0:
        B.append(A[n])
    else:
        B.appendleft(A[n])
print(*B)

### FIXED CODE ###

from collections import deque

N = int(input())
A = [int(a) for a in input().split()]
B = deque([])
for n in range(N):
    if n % 2 == 0:
        B.append(A[n])
    else:
        B.appendleft(A[n])
if N % 2 == 0:
    print(*B)
else:
    print(*list(B)[::-1])
N = int(input())
S = lisr(input())
cnt = 0
for i in range(1, N-1):
    if S[i-1] == "#" and S[i] == ".":
        s[i] = "."
         cnt += 1
print(cnt)

### FIXED CODE ###

A, B, C = map(int, input().split())
if A > B:
    tmp = A
    A =  B
    B = tmp 

if C >= A and C <= B:
    print("Yes")
else:
    print("No")
a = [input() for i in range(3)]
print(a[0]*a[1]/2)

### FIXED CODE ###

a = list(int(i) for i in input().split())
print(a[0]*a[1]//2)
fast_list = list(map(int, input().split())) 
correct_answer_count = 0
for i in range(1, fast_list[0] + 1):
    bat_answer_count = 0
    for j in range(1, i+1):
        if not (fast_list[1][i] <= fast_list[1][j]):
            bat_answer_count += 1

if bat_answer_count == 0:
    correct_answer_count += 1

print(correct_answer_count)    


### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
 
cnt = 0
p_min = p[0]
for i in range(n):
  pi = p[i]
  if pi <= p_min:
    cnt += 1
    p_min = pi
print(cnt)
if input().issuper():
  print("a")
else:
  print("a")

### FIXED CODE ###

if input().isupper():
  print("A")
else:
  print("a")
n=int(input())
s,t=input().split()
u=''
for i in range(n):
  u.append(s[i])
  u.append(t[i])
print(u)

### FIXED CODE ###

n=int(input())
s,t=input().split()
u=''
for i in range(n):
  u+=s[i]
  u+=t[i]
print(u)
cannot understand the q

### FIXED CODE ###



import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r

left = max(L)
right = min(R)

if left <= right:
    print(right-left+1)
else:
    print(0)
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

check_i = []
check_j = []
for i in range(H):
    if i == 0:
        check_i = [0, 1]
    elif i == H-1:
        check_i = [i-1, i]
    else:
        check_i = [i-1, i, i+1]
    for j in range(W):
        if S[i][j] == "#":
            continue

        if j == 0:
            check_j = [0, 1]
        elif j == W-1:
            check_j = [j-1, j]
        else:
            check_j = [j-1, j, j+1]
        
        count = 0
        for k in check_i:
            for l in check_j:
                if S[k][l] == "#":
                    count += 1
        S[i][j] = str(count)

for i in range(H):
    print("".join(S[i]))

### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for i in range(H)]

check_i = []
check_j = []
for i in range(H):
    if H == 1:
        check_i = [0]
    elif i == 0:
        check_i = [0, 1]
    elif i == H-1:
        check_i = [i-1, i]
    else:
        check_i = [i-1, i, i+1]
    for j in range(W):
        if S[i][j] == "#":
            continue

        if W == 1:
            check_j = [0]
        elif j == 0:
            check_j = [0, 1]
        elif j == W-1:
            check_j = [j-1, j]
        else:
            check_j = [j-1, j, j+1]
        
        count = 0
        for k in check_i:
            for l in check_j:
                if S[k][l] == "#":
                    count += 1
        S[i][j] = str(count)

for i in range(H):
    print("".join(S[i]))
n = int(input())
x = [0] * n
y = [0] * n
h = [0] * n
for i in range(n):
    x2, y2, h2 = map(int, input().split())
    x[i] = x2
    y[i] = y2
    h[i] = h2
ans = [0,0,0]
for i in range(101):
    for j in range(101):
        l = 0
        while h[l] == 0:
            l += 1
        #print(l)
        val = h[l] + abs(i-x[l]) + abs(j-y[l])
        flg = True
        for k in range(n):
            if val != h[k] + abs(i-x[k]) + abs(j-y[k]) and h[k] != 0:
                flg = False
            if h[k] == 0 and val != abs(i-x[k]) + abs(j-y[i]) and val - abs(i-x[k]) - abs(j-y[k]) == 0:
                flg = False
        if flg == True:
            ans = [i,j,val]
print(' '.join(map(str,ans)))


### FIXED CODE ###

n = int(input())
x = [0] * n
y = [0] * n
h = [0] * n
for i in range(n):
    x2, y2, h2 = map(int, input().split())
    x[i] = x2
    y[i] = y2
    h[i] = h2
ans = [0,0,0]
for i in range(101):
    for j in range(101):
        l = 0
        while h[l] == 0:
            l += 1
        #print(l)
        val = h[l] + abs(i-x[l]) + abs(j-y[l])
        flg = True
        for k in range(n):
            if val != h[k] + abs(i-x[k]) + abs(j-y[k]) and h[k] != 0:
                flg = False
            if h[k] == 0 and abs(i-x[k]) + abs(j-y[k]) < val:
                flg = False
        if flg == True:
            ans = [i,j,val]
print(' '.join(map(str,ans)))
import math
from functools import reduce

n, x = map(int,input().split())
a = list(map(int,input().split()))

for i in range(len(a)):
	a[i] = abs(a[i] - x)

print(reduce(math.gcd, a))

### FIXED CODE ###

import fractions
from functools import reduce

n, x = map(int,input().split())
a = list(map(int,input().split()))

for i in range(len(a)):
	a[i] = abs(a[i] - x)

print(reduce(fractions.gcd, a))