Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# coding: utf-8
# Your code here!

from collections import Counter

n = int(input())
s = [input() for i in range(n)]
s = sorted(s)
c = Counter(s)
c_values = c.values()
for j in c.items():
    if j[1] == max(c_values):
        print(j[0])

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import Counter

n = int(input())
s = [input() for i in range(n)]
c = Counter(s)
c_max = max(c.values())
ans = [j[0] for j in c.items() if j[1] == c_max]
ans = sorted(ans)
for f in ans:
    print(f)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
s=list(input())
t=list(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
dps=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            dps[i+1][j+1]=dps[i][j]+1
        else:
            if (dps[i+1][j])>(dps[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
                dps[i+1][j+1]=dps[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
                dps[i+1][j+1]=dps[i][j+1]
print(dp[n][m])


### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()
### BUGGY CODE ###

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
ans = [p+q+r for p in a for q in b for r in c]

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


### FIXED CODE ###

x , y ,z , k = map(int, input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

e = [i + j for i in a[:k] for j in b[:k]]
e.sort(reverse=True)
e = e[:k]
ans = [i + j for i in e for j in c[:k]]
ans.sort(reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import itertools
N,K=map(int,input().split())
L=[]
n=0
while n<N:
  L.append(int(input()))
  n=n+1
ans=[]
for r in list(itertools.combinations(L,K)):
  ans.append(max(r)-min(r))
print(min(ans))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
ans=[]
for i in range(len(h)-K+1):
  b=h[K+i-1]-h[i]
  ans.append(b)
print(min(ans))
### BUGGY CODE ###

N = int(input())
C=list(input())
X=[0]*(N+1)
for i in range(N+1):
  W=(C[:i].count('W'))
  R=(C[i:].count('R'))
  X[i]=max(W,R)
print(min(X))

### FIXED CODE ###

N = int(input())
C=list(input())
type=set(C)
L=0
R=0
RR=0
X=0
if 'R' in type and 'W' in type:
    for i in range(N):
      L=i
      R=RR
      if L>=N-1-R:
        break
      if C[i]=='W':
          for ii in range(N-L-R):
            if C[N-1-R-ii]=='R':
              C[L]='R'
              C[N-1-R-ii]='W'
              X+=1
              break
            RR+=1
            if L>=N-1-R:
              break
print(X)
### BUGGY CODE ###

A,B,K=map(int,input().split())
for i in range(K):
    if  A==0 and B==0:
        A+=0
        B+=0
    elif A>=1:
        A-=1
    elif B>=1:
        B-=1
c=str(A)
d=str(B)
print(c+' '+d)

### FIXED CODE ###

A,B,K=map(int,input().split())
if A>=K:
    c=A-K
    d=B
elif A==0 and B>=K:
    c=0
    d=B-K
elif A+B<=K:
    c=0
    d=0
else:
    d=B-(K-A)
    c=0
print(str(c)+' '+str(d))
### BUGGY CODE ###

import collections
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * 10**(N - n - 1)) % P for n in range(N)]
    T = [0]
    for n in range(N)[::-1]:
        T.append((T[-1] + S[n]) % P)
    T.reverse()
    ans = 0
    T = collections.Counter(T).values()
    for v in T:
        ans += v * (v - 1) // 2
    print(ans)


### FIXED CODE ###

N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)
### BUGGY CODE ###

N = int(input())
A=[]
for i in range(N):
    x= sorted(list(input()))
    A.append(x)
ans = 0
for i in range(N):
    ans += A[i+1:].count(A[i])
print(ans)

### FIXED CODE ###

import collections
N = int(input())
A=[]
for i in range(N):
    x= str(sorted(input()))
    A.append(x)
B=collections.Counter(A)
ans = 0
for i in B.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = []
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '#':
      wall.add((x, y))
    else:
      start.append((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy[0],xy[1],0))
  step = 0
  already = set() | wall
  while len(d) > 0:
    now = d.popleft()
    already.add(now[:-1])
    step = now[2]+1
    for xs, ys in ssize:
      x,y = now[0]+xs, now[1]+ys
      if (x, y) not in already and 0 <= x < W and 0 <= y < H:
        d.append((x, y, step))
  score = max(step-1, score)
  
print(score)

### FIXED CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
 
route = []
for _ in range(H):
  route.append(input())
  
wall = set()
start = set()
for y, r in enumerate(route):
  for x, w in enumerate(r):
    if w == '.':
      start.add((x, y))

score = -1
ssize = [(-1,0),(0,-1),(1,0),(0,1)]
for xy in start:
  d = deque()
  d.append((xy+(0,)))
  step = 0
  can = copy.deepcopy(start)
  can.remove(xy)
  while len(d) > 0:
    now = d.popleft()
    step = now[2]
    for xs, ys in ssize:
      nxt = (now[0]+xs, now[1]+ys)
      if nxt in can:
        d.append(nxt+(step+1,))
        can.remove(nxt)
  score = max(step, score)
  
print(score)
### BUGGY CODE ###

s = input()
for i in range(len(s)):
    if s[i] == "?":
        s = s[:i] + 'D' + s[i+1:]
print(s)

### FIXED CODE ###

s = input()
print(s.replace('?', 'D'))
### BUGGY CODE ###

from itertools import combinations
N=int(input())
A=list(map(int,input().split()))


ans=0
for i in range(N-1):
    ans+=A[i]*(sum(A[i+1:]))

print(ans%(10**9+7))    

### FIXED CODE ###

from itertools import combinations
N=int(input())
A=list(map(int,input().split()))

zen=sum(A)


ans=0
part=0
for i in range(N-1):
    part+=A[i]
    ans+=A[i]*(zen-part)

print(ans%(10**9+7))
### BUGGY CODE ###

n=int(input())
h= list(map(int,input().split()))
count=[0]*n

for t in range(n):
    for i in range(t,n-1):
        if h[i]>=h[i+1]:
            count[t]+=1
        else:
            break

print(max(count))


### FIXED CODE ###

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

COU=0
m_max=0
for i in h:
    if i>COU:
        m=0
    else:
        m+=1
        if m>m_max:
            m_max=m
    
    COU=i
print(m_max)
### BUGGY CODE ###

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

for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))

A.sort()

for i in range(1,N+1):
  print(bisect_right(A,i) - bisect_left(A,i))
### BUGGY CODE ###

N = int(input())

def gcd (a,b):
  if a < b: a, b = b, a
  while b:
    a,b = b, a % b
  return a
print (sum([gcd(gcd(x,y),z) for x in range(1,N+1)  for y in range(1,N+1)  for z in range(1,N+1)]))


### FIXED CODE ###

N = int(input())
L = [[1]* 201 for _ in range(201)] 

def gcd (a,b):
  if a < b:
    a, b = b, a
  A, B = a, b
  if L[a][b] != 1:
    return L[a][b]
  while b:
    a,b = b, a % b
  L[A][B] = a
  return a

ans = 0
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      t = gcd(x,y)
      u = gcd(t,z)
      ans += u
print (ans)
### BUGGY CODE ###

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

def main():
    n, m = map(int, input().split())
    ans = set([i for i in range(1 , n + 1)])
    for _ in range(m):
        l, r = map(int, input().split())
        card = set([i for i in range(l, r + 1)])
        ans = ans & card
    print(len(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def solve(l1, r1, l2, r2):
    if r1 < l2 or r2 < l1:
        return None
    elif l1 < l2 and r1 < r2:
        return [l2, r1]
    elif l1 >= l2 and r1 <= r2:
        return [l1, r1]
    elif l1 <= l2 and r2 <= r1:
        return [l2, r2]
    else:
        return [l1, r2]


def main():
    n, m = map(int, input().split())
    ans = [1, n]
    for _ in range(m):
        l, r = map(int, input().split())
        # print(l, r)
        ans = solve(ans[0], ans[1], l, r)
        # print(ans)
        if ans is None:
            print(0)
            exit(0)
    print(ans[1] - ans[0] + 1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

if __name__ == '__main__':
    A, B, K = map(int, input().split())

    candidates = {v for v in range(A, B + 1)}

    satisfied_integers = set()
    for i in range(K):
        satisfied_integers |= {A + i}

    for i in range(K):
        satisfied_integers |= {B - K + 1 + i}
        
    satisfied_integers = sorted(candidates & satisfied_integers)
    for v in satisfied_integers:
        print(v)


### FIXED CODE ###

if __name__ == '__main__':
    A, B, K = map(int, input().split())

    satisfied_integers = set()
    for i in range(K):
        if A + i <= B:
            satisfied_integers |= {A + i}
            
        if A <= B - K + 1 + i:
            satisfied_integers |= {B - K + 1 + i}

    satisfied_integers = sorted(satisfied_integers)
    for v in satisfied_integers:
        print(v)
### BUGGY CODE ###

n,m=map(int,input().split())
ps=[list(map(int, input().replace('AC','1').replace('WA','-1').split())) for i in range(m)]

pAC=[]
pWA=[]
for i in range(m):
  if ps[i][1]==1 and ps[i][0] not in pAC:
    pAC+=[ps[i][0]]
  elif ps[i][1]==-1 and ps[i][0] not in pAC:
    pWA+=[ps[i][0]]

pWA2=[]
for i in pWA:
  if i in pAC:
    pWA2+=[i]
pWA=pWA2
print(len(set(pAC)),len(pWA))

### FIXED CODE ###

n,m=map(int,input().split())
ps=[list(map(int,input().replace('WA','0').replace('AC','1').split())) for i in range(m)]
ps.sort(key=lambda x:x[0])

tmp_p=0
ac_cnt=0
wa_cnt=0
wa=0
flg=0
for i in range(m):
  p=ps[i][0]
  s=ps[i][1]
  if tmp_p!=p:
    wa=0
    flg=0
  if s==1 and flg==0:
    flg=1
    ac_cnt+=1
    wa_cnt+=wa
  elif s==0 and flg==0:
    wa+=1
  tmp_p=p
print(ac_cnt, wa_cnt)
### BUGGY CODE ###

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

mod = 10**9 + 7
ans = 0
for i in range(n):
  for j in range(i+1,n):
    ans += (a[i] * a[j])
    ans = ans % mod
    
print(ans)

### FIXED CODE ###

n = int(input())
a = tuple(map(int,input().split()))
t = 0
mod = 10**9 + 7
at = []
for j in range(1,n):
  t += a[n-j] % mod 
  at.append(t)

ans = 0
for i in range(n-1):
  ans += at[n-2-i] *a[i]
print(ans % mod)
### BUGGY CODE ###

from collections import Counter
N, K = list(map(int, input().split()))
C = Counter()
for _ in range(N):
    a, b = list(map(int, input().split()))
    C += {a: b}
# print(C)
L = list(C.keys())
L.sort()
i = 0
ct = C[L[0]]
while ct < K:
    i += 1
    ct += C[L[i]]
print(L[i])


### FIXED CODE ###

N, K = list(map(int, input().split()))
C = [0]*(10**5+1)
S=set()
for _ in range(N):
    a, b = list(map(int, input().split()))
    C[a] += b
    S.add(a)

L = list(S)
L.sort()
i = 0
ct = C[L[0]]
while ct < K:
    i += 1
    ct += C[L[i]]
print(L[i])
### BUGGY CODE ###

def two_power(m):
  if m < 2:
    return 0
  else:
    return two_power(m//2) + 1
  
def nibun(x, *args):
  l = len(args)
  if l == 0:
    return -float('inf')
  elif args[l // 2] == x:
    return l // 2
  elif args[l // 2] < x:
    b = args[:l //2]
    return nibun(x, *b)
  else:
    b = args[l // 2+1:]
    return l // 2 + 1 + nibun(x, *b)
  
n = int(input())
a = list(map(int, input().split()))

a.sort()
a.reverse()
c = 0
skip = []
for i in range(len(a)):
  if a[i] == -1:
    break
  m = two_power(a[i])
  x = 2 ** (m+1) - a[i]
  b = a[i+1:]
  index = nibun(x, *b)
  if index >= 0:
    c += 1
    a.pop(i + 1 +index)
    a.append(-1)

print(c)



### FIXED CODE ###

from collections import defaultdict
import math

n = int(input())
a_list = list(map(int, input().split()))
d = defaultdict(int)

for a in a_list:
  d[a] += 1

a_list = reversed(sorted(list(set(a_list))))
c = 0
for a in a_list:
  m = int(math.log(a, 2))
  x = 2 ** (m+1) - a
  if x == a:
    c += d[a] // 2
    d[a] -= d[a] // 2
  else:
    c += min(d[x], d[a])
    d[x] -= min(d[x], d[a])

print(c)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
c = 0

for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if z >= 0 and z <= k:
            c += 1
print(c)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10*5]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-k),i))
print(dp[n-1])


### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[10**5]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-k),i))
print(dp[n-1])
### BUGGY CODE ###

import copy

N=int(input())

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

ans=copy.deepcopy(li)

for n in range(N):
  x=li[n]
  ans.pop(x-1)
  ans.insert(x-1,n+1)

print(*ans)

### FIXED CODE ###

import copy

N=int(input())

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

ans=copy.copy(li)

ans=sorted(range(N), key=lambda k: li[k])

for n in range(N):
  ans[n]+=1
      
print(*ans)
### BUGGY CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += len(S[:j])
    else:
        S = S[::-1]
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S):
            # print(i, s)
            s = int(s)
            acc[i+1] = (s * d + acc[i]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
    t=0
    for j,v in e(b[:a+1]):
      t+=v
      t%=M
      d[j]=t
    for j,(w,v)in e(zip(b,b[a+1:]),a+1):
      t+=v-w
      t%=M
      d[j]=t
  print(t)
main()

### FIXED CODE ###

def main():
  e,M=enumerate,10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[0]*(k+1)for _ in range(n+1)]
  dp[0][0]=1
  for i,(b,d,a)in e(zip(dp,dp[1:],a),1):
    t=0
    for j,v in e(b):
      t+=v
      if j>a:t-=b[~a+j]
      t%=M
      d[j]=t
  print(t)
main()
### BUGGY CODE ###

n=int(input())
s=input()
lst=list(s)
r=[i for i,j in enumerate(lst) if j=="R"]
g=[i for i,j in enumerate(lst) if j=="G"]
b=[i for i,j in enumerate(lst) if j=="B"]
comb=len(r)*len(g)*len(b)
out=0
for i in r:
  for j in g:
    for k in b:
      if (i+j)==2*k or (j+k)==2*i or (k+i)==2*j:
        out+=1
print(comb-out)


### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b
for i in range(n-2):
  for j in range(i+1,n):
    k=2*j-i
    if k>(n-1):
      break
    if s[i]!=s[j]!=s[k]!=s[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

def isOK(index,key,li):
    if li[index] >= key:
        #不等号にイコールを入れないとokはliの中でkey以下の数字がいくつあるかを表し、
        #ここの不等号にイコールを入れると
        #okはliの中でkey未満の数字がいくつあるかを表すようになる
        return True
    else:
        return False
def binary_search(key,li):
    ng = -1
    ok = len(li)
    while abs(ok - ng) > 1:
        mid = ok + ng //2
        if isOK(mid,key,li):
            ok = mid
        else:
            ng = mid
    return ok
    #liはsortしておくことに注意


def isOK2(index,key,li):
    if li[index] > key:
        #不等号にイコールを入れないとokはliの中でkey以下の数字がいくつあるかを表し、
        #ここの不等号にイコールを入れると
        #okはliの中でkey未満の数字がいくつあるかを表すようになる
        return True
    else:
        return False
def binary_search2(key,li):
    ng = -1
    ok = len(li)
    while abs(ok - ng) > 1:
        mid = ok + ng //2
        if isOK2(mid,key,li):
            ok = mid
        else:
            ng = mid
    return ok
    #liはsortしておくことに注意
n = I()
a_li = sorted(LI())
b_li = sorted(LI())
c_li= sorted(LI())
p = len(c_li)
ans = 0
for i in range(n):
    B = b_li[i]
    k = p - binary_search2(B,c_li)
    l = binary_search(B,a_li)
    ans += k*l
print(ans)


### FIXED CODE ###

import bisect

def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = I()
a_li = sorted(LI())
b_li = sorted(LI())
c_li= sorted(LI())
ans = 0
for i in range(n):
  B = b_li[i]
  k = n - bisect.bisect_right(c_li,B)
  l = bisect.bisect_left(a_li,B)
  ans += k*l
print(ans)
### BUGGY CODE ###

h, w= map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
B = [list(map(int, input().split())) for _ in range(h)]

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

d = 80*(h+w-1)
D = 2*d+1
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][d+C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][k-C[i+1][j]] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][k-C[i][j+1]] = 1
ans = d
for i in range(d, D):
    if dp[-1][-1][i] != 0:
        ans = min(ans, i-d)
for i in reversed(range(d)):
    if dp[-1][-1][i] != 0:
        ans = min(ans, d-i)
print(ans)

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
A = [0]*h
B = [0]*h
for _ in range(h):
  A[_] = list(map(int, input().split()))
  
for _ in range(h):
  B[_] = list(map(int, input().split()))

C = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    C[i][j] = abs(A[i][j]-B[i][j])
    
dp = [[0]*w for _ in range(h)]
D = 80 * (h + w)
L = 2*D + 1
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][D+C[0][0]] = 1
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue
    x = np.zeros(L, np.bool)
    if i != 0:
      x[C[i][j]:] |= dp[i-1][j][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i-1][j][C[i][j]:]
    if j != 0:
      x[C[i][j]:] |= dp[i][j-1][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i][j-1][C[i][j]:]
    dp[i][j] = x
    
temp = np.where(dp[-1][-1]>0)[0]-D
temp = np.abs(temp)
print(np.min(temp))
### BUGGY CODE ###

N = int(input())
cnt = 0
for i in range(2, N+1):
    m = N//i
    e = N%i
    if m==e:
        cnt +=i
print(cnt)        

### FIXED CODE ###

import numpy as np
N = int(input())
cnt = 0
for i in range(1, int(np.ceil(np.sqrt(N)))):
    if (N-i)%i ==0 and (N-i)/i >i:
        cnt += int((N-i)/i)
print(cnt)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
arr = [1 for _ in range(n)]
for _ in range(m):
    l, r = MAP()
    for i in range(l - 1):
        arr[i] = 0
    for i in range(r, n):
        arr[i] = 0
print(sum(arr))

### FIXED CODE ###

#https://atcoder.jp/contests/abc127/tasks/abc127_c

NM = [int(i) for i in input().split()]
LR = []
for i in range(NM[1]):
    LR.append([int(i) for i in input().split()])

mi = LR[0][0]
ma = LR[0][1]
for i in range(NM[1]):
    if LR[i][0] > mi:
        mi = LR[i][0]
    if LR[i][1] < ma:
        ma = LR[i][1]

'''
if ma > NM[0]:
    ma = NM[0]
if mi > NM[0]:
    mi = ma + 1
print(ma - mi + 1)
'''
if ma < mi:
    print(0)
elif NM[0] >= ma:
    print(ma-mi+1)
elif NM[0] < ma and NM[0] > mi:
    print(NM[0]-mi+1)
elif NM[0] <= mi:
    print(0)