Harryxun/stf_run huggingface dataset:
def ret(a,b,c):
  global c2,c3
  if a == b:
    if b == "0":
      return "1"
   	else:
      return "0"
    if c == 2:
      c2 += 1
    else:
      c3 += 1
  else:
    return b
S = input()
S2,S3 = list(S),list(S)
c2,c3 = 0,0
default = S2[0]
for j,k in enumerate(S2):
  if j == 0:
    continue
  S2[j] = ret(S2[j-1],k,2)
for j,k in enumerate(S3):
  if j == 0:
    S3[0] = ret(default,S3[0])
  S3[j] = ret(S3[j-1],k,3)
print(c2 if c2 >= c3 else c3)

### FIXED CODE ###

c2,c3 = 0,0
def ret(a,b,c):
  global c2,c3
  if a == b:
    if c == 2:
      c2 += 1
    else:
      c3 += 1
    if b == "0":
      return "1"
    else:
      return "0"
  else:
    return b
S = input()
S2,S3 = list(S),list(S)
default = S2[0]
for j,k in enumerate(S2):
  if j == 0:
    continue
  S2[j] = ret(S2[j-1],k,2)
for j,k in enumerate(S3):
  if j == 0:
    S3[0] = ret(default,S3[0],3)
  S3[j] = ret(S3[j-1],k,3)
print(c2 if c2 <= c3 else c3)
if N % 500 <= A:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
a = int(input())

if n % 500 <= a:
    print("Yes")
else:
    print("No")
N,M = map(int,input().split())
a = list(map(int, input().split()))
for i in range(M+1):
  N -= a[i]
print(N if N>0 else '-1')


### FIXED CODE ###

N,M = map(int,input().split())
a = list(map(int, input().split()))
for i in range(M):
  N -= a[i]
print(N if N>=0 else '-1')
r = int(input())
import math
PI = math.pi
S = r * r * PI
L = 2 * r * PI
print("%f %f" % (S, L))


### FIXED CODE ###

r = float(input())
import math
PI = math.pi
S = r * r * PI
L = 2 * r * PI
print("%f %f" % (S, L))
n = int(input())
r = int(input())
if n > 9:
  print(r)
else:
  print(r+100*(10-n))

### FIXED CODE ###

n,r = map(int,(input().split()))
if n > 9:
  print(r)
else:
  print(r+100*(10-n))
t = str(input())

p_num = t.count("P")
d_num = t.count("D")
h_num = t.count("?")

if p_num<d_num:
  p_num += h_num
else :
  d_num += h_num
  
if p_num>d_num:
  swap(p_num, d_num)
  
for i in range(p_num):
  print("PD")

for i in range(d_num-p_num):
  print("D")

### FIXED CODE ###

t = input()

t = t.replace('?', 'D')
print(t)
import collections
N, K, L = map(int, input().split())
road = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]
rail = [{"Connected":[],"set":-1,"seen":False} for i in range(N)]

def dfs(node, num): #深さ優先探索
    node["seen"] = True
    node["set"] = num
    for next_node in node["Connected"]:
        if next_node["seen"]:
            continue
        dfs(next_node, num)

for i in range(K):
    p, q = map(int, input().split())
    road[p-1]["Connected"].append(road[q-1])
    road[q-1]["Connected"].append(road[p-1])
for i in range(L):
    r, s = map(int, input().split())
    rail[r-1]["Connected"].append(rail[s-1])
    rail[s-1]["Connected"].append(rail[r-1])
for X in [road, rail]: #連結成分に分解
    set_index = 0
    for x in X:
        if x["seen"]:
            continue
        dfs(x, set_index)
        set_index += 1
List = [(road[i]["set"],rail[i]["set"]) for i in range(N)]
counter = collections.Counter(List)
for A in List:
    print(counter[A],end=" ")
        


### FIXED CODE ###

N, K, L = map(int, input().split())

def fp(x, parentList): #findParent
    if parentList[x] == x:
        return x
    else:
        parentList[x] = fp(parentList[x], parentList)
        return parentList[x]

#各ノードのparentをリストで表現(連結前は自身がparent)
road = [i for i in range(N)]
rail = [i for i in range(N)]

for _ in range(K):
    p, q = map(int, input().split())
    par_p, par_q = fp(p-1, road), fp(q-1, road) #p, qのparent 
    #連結する際、若い番号をparentとする
    if par_p < par_q:
        road[par_q] = par_p
    else:
        road[par_p] = par_q

#railについても同様
for _ in range(L):
    s, t = map(int, input().split())
    par_s, par_t = fp(s-1, rail), fp(t-1, rail)
    if par_s < par_t:
        rail[par_t] = par_s
    else:
        rail[par_s] = par_t

#連結成分の要素をカウント
cnt = {}
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    if key in cnt:
        cnt[key] += 1
    else:
        cnt[key] = 1
#出力
for i in range(N):
    key = (fp(i,road),fp(i,rail))
    ans = cnt[key]
    print(ans, end=" ")
N = int(input())
A = sorted(list(map(int, input().split())))

for i in range(N-1):
    A[i+1] = (A[i] + A[i+1])/2

 print(A[N-1])

### FIXED CODE ###

n = int(input())
v = sorted(list(map(int, input().split())))

for i in range(n - 1):
    v[i + 1] = (v[i] + v[i + 1]) / 2

print(v[n - 1])
X=input()

if X=>30 :
  print("Yes")
else :
  print("No")
  
  

### FIXED CODE ###

print("Yes") if int(input()) >= 30 else print("No")
n = int(input())
h = [int(i) for i in input().split()]
for j in range(n):
  if h[j] - h[j+1] > 1:
    print("No")
    exit()
  else:
    continue
for k in range(n-1):
  if h[k] > h[k+1] and h[k+1] > h[k+2]:
    print("No")
    exit()
  else:
    continue
print("Yes")


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
for j in range(n-1):
  if h[j] - h[j+1] > 1:
    print("No")
    exit()
  elif h[j] == h[j+1] + 1:
    h[j+1] += 1
print("Yes")
s = input().split()
print(len(set(s))

### FIXED CODE ###

s = input().split()
print(len(set(s)))
import sys, os

if __name__ == '__main__':
    N = input()
    s = 0
    for i in range(1, N+1):
        if i % 3 ==0 or i % 5 ==0:
            continue
        else:
            s += i
    print(s)


### FIXED CODE ###

import sys, os

if __name__ == '__main__':
    N = int(input())
    s = 0
    for i in range(1, N+1):
        if i % 3 ==0 or i % 5 ==0:
            continue
        else:
            s += i
    print(s)
n, k = map(int, input().split())
a = list(map(int, input().split()))

length = [-1] * n
path = [-1, -1]
route = []


def func(now, depth):
    global path, length, a, route
    route.append(now)
    if length[now] == -1:
        length[now] = depth
        func(a[now]-1, depth+1)
    else:
        path = [length[now], depth - length[now]]


func(0, 0)

print(route[path[0]+(k-path[0]) % path[1]]+1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, k = map(int, input().split())
a = list(map(int, input().split()))

length = [-1] * n
path = [-1, []]
route = []


def func(now, depth):
    global path, length, a, route
    route.append(now)
    if length[now] == -1:
        length[now] = depth
        func(a[now]-1, depth+1)
    else:
        path = [length[now], route[length[now]:depth]]


func(0, 0)

if (k < path[0]):
    print(route[k] + 1)
else:
    tmp = k - path[0]
    tmp %= len(path[1])
    print(path[1][tmp] + 1)
a, b = map(int, input().split())
h = [sum(range(i)) for i in range(1, 1000)]
print(h[b - a] - b)

### FIXED CODE ###

a, b = map(int, input().split())
h = [sum(range(i + 1)) for i in range(1, 1000)]
print(h[b - a - 2] - a)
n=int(input())
print(int (n(n+1)/2))

### FIXED CODE ###

n=int(input())
print(int (n*(n+1)/2))
import sys
n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]

ab.sort(key=lambda x: x[1])
now = 0 #現在時刻
for i in range(n):
    now = now + ab[i][0]
    if now > ab[i][1]:
        print('No')
        sys.exit()

print('Yes')


### FIXED CODE ###

s = str(input())
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
    print("Bad")
else:
    print("Good")
n, a, b = map(int, input().split())
list = [0] * n
idx = 0
while True :
    if a < list.count(0) :
        for i in range(idx,idx+a) :
            list[i] = "b"
        idx += a
    elif a == list.count(0) :
        for i in range(idx,idx+a) :
            list[i] = "b"
        break
    else :
        for i in range(idx,idx+list.count(0)) :
            list[i] = "b"
        break

    if b < list.count(0) :
        for i in range(idx,idx+b) :
            list[i] = "a"
        idx += b
    elif b == list.count(0) :
        for i in range(idx,idx+b) :
            list[i] = "a"
        break
    else :
        for i in range(idx,idx+list.count(0)) :
            list[i] = "a"
        break
print(list.count("b"))


### FIXED CODE ###

n, a, b = map(int, input().split())
red = 0 ; blue = 0
if n >= a + b :
    stack = n // (a+b)
    red += b * stack
    blue += a * stack
    n -= (a+b) * stack
if n > a :
    n -= a
    blue += a
else :
    blue += n
if n > b :
    n -= b
    red += b
else :
    red += n
print(blue)
N, K = map(int, input().split())
d = []
A = []

for i in range(K):
    d.append(int(input()))
    A.append(list(map(int, input().split())))

okashi = [0] * N

for l in range(N):
    for i in A[l]:
        okashi[i-1] += 1

count = 0
for i in okashi:
    if i == 0:
        count += 1

print(count)


### FIXED CODE ###

N, K = map(int, input().split())
d = []
A = []

for i in range(K):
    d.append(int(input()))
    A.append(list(map(int, input().split())))

okashi = [0] * N

for l in range(K):
    for i in A[l]:
        okashi[i-1] += 1

count = 0
for i in okashi:
    if i == 0:
        count += 1

print(count)
n = int(input())
node = [[] for _ in range(n)]
edge = []
for i in range(n-1):
    a,b = map(lambda x:int(x)-1, input().split())
    edge.append((a,b))
    node[a].append(b)
    node[b].append(a)
k = max(len(i) for i in node)
print(k)
node = [set(range(1,k+1)) for _ in range(n)]
for i,j in edge:
    tmp = (node[i]&node[j]).pop()
    node[i].remove(tmp)
    node[j].remove(tmp)
    print(tmp)

### FIXED CODE ###

import sys
n = int(input())
sys.setrecursionlimit(2*n)
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(lambda x:int(x)-1, input().split())
    graph[a].append((b, i))
    graph[b].append((a, i))

def DFS(node, p_node=-1, p_color=-1):
    color = 1
    for c_node, edge in graph[node]:
        if c_node==p_node:
            continue
        if color==p_color:
            color += 1
        ans[edge] = color
        DFS(c_node, node, color)
        color += 1
ans = [0]*(n-1)
DFS(0)
k = max(len(i) for i in graph)
print(k)
[print(i) for i in ans]
N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
li = [0] * M
for i in range(M):
    B,C = [int(j) for j in input().split()]
    li[i] = [C,B]
li.sort()
li.reverse()
A.sort()
Ba = [0] * M
for i in range(M):
    Ba[i] = li[i][1]
from numpy import cumsum
from bisect import bisect_left
B_sum = list(cumsum(Ba))
count = B_sum[-1]
N = min(N,count)
for i in range(N):
    indexa = bisect_left(B_sum,i+1)
    if A[i] >= li[indexa][0]:
        break
    if A[i] < li[indexa][0]:
        A[i] = li[indexa][0]
print(sum(A))

### FIXED CODE ###

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

cb_dict = {}
for _ in range(m):
    b, c = map(int, input().split())
    new = {c:b}
    if c in cb_dict.keys():
        cb_dict[c] += b
    else:
        cb_dict.update(new)

cb_dict = sorted(cb_dict.items(), key=lambda x:x[0], reverse=True)

now_c = 0
now_b = 0
for i in range(n):
    if A[i] >= cb_dict[now_c][0]:
        break
    else:
        A[i] = cb_dict[now_c][0]
        now_b += 1
        if now_b == cb_dict[now_c][1]:
            now_c += 1
            now_b = 0
        if now_c > len(cb_dict)-1:
            break

ans = sum(A)
print(ans)
n=input()
l=[0]+list(map(int,input().split()))+[0]
ans=0
pre=0
for i in l:ans+=abs(pre-i);pre=i
for i in range(1,int(n)+1):
  dif=-abs(l[i]-l[i-1])-abs(l[i]-l[i+1])+abs(l[i-1]-l[i+1])
  if l[i]in(l[i-1],l[i+1]):print(ans)
  elif l[i]<l[i-1]:
    print(ans if l[i+1]<l[i] else ans+dif)
  else:print(ansans if l[i+1]>l[i] else ans+dif)

### FIXED CODE ###

n=int(input())
l=[0]+list(map(int,input().split()))+[0]
ans=0
for a,s in zip(l,l[1:]):
    ans+=abs(a-s)
for i in range(n):
    a,s=sorted([l[i],l[i+2]])
    if a<=l[i+1]<=s:print(ans)
    else:
        print(ans-abs(a-l[i+1])-abs(l[i+1]-s)+s-a)
n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = W - w1 * j
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)


### FIXED CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

dp = [[[-1] * (3 * n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
w1 = wv[0][0]

for i, (w, v) in enumerate(wv):
    for j in range(i + 1):
        for k in range(3 * n + 1):
            if dp[i][j][k] != -1:
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
                w_diff = w - w1
                if j + 1 <= n and k + w_diff <= 3 * n:
                    dp[i+1][j+1][k+w_diff] = max(dp[i+1][j+1][k+w_diff], dp[i][j][k] + v)

ans = 0
for j in range(n + 1):
    w_diff_mx = min(W - w1 * j, 3 * n)
    for k in range(w_diff_mx + 1):
        ans = max(ans, dp[n][j][k])

print(ans)
N, L = map(int, input().split())
s = []
for i in range(L):
    line = input()
    print(line)
    s.append(line)
s.sort()
print("".join(s))

### FIXED CODE ###

N, L = map(int, input().split())
S = []
for i in range(N):
    line = input()
    S.append(line)
S.sort()
print("".join(S))
def moov(x,y):
    if (x,y) in Loc:
        return "LOOP"
    else:
        Loc.append((x,y))
        if Room[y][x] == ".":
            return str(x)+" "+str(y)
        elif Room[y][x] == ">":
            return moov(x + 1,y)
        elif Room[y][x] == "<":
            return moov(x - 1,y)
        elif Room[y][x] == "^":
            return moov(x,y - 1)
        elif Room[y][x] == "v":
            return moov(x,y + 1)
    

while True:
    Loc = []
    num = 0
    Room = []
    h,w = map(int,input().split())
    if h == w == 0:
        break
    for i in range(h):
        vec = input()
        Room.append(list(vec))
    print(moov(1,0))

### FIXED CODE ###

def move(Tiles_map, x, y, Loop_ch):
    if [x,y] in Loop_ch:
        print("LOOP")
        return
    else:
        Loop_ch.append([x,y])

    if Tile_map[x][y] == ".":
        print(str(y) + " " + str(x))
        return
    elif Tile_map[x][y] == ">":
        move(Tiles_map, x, y+1, Loop_ch)
    elif Tile_map[x][y] == "<":
        move(Tiles_map, x, y-1, Loop_ch)
    elif Tile_map[x][y] == "v":
        move(Tiles_map, x+1, y, Loop_ch)
    elif Tile_map[x][y] == "^":
        move(Tiles_map, x-1, y, Loop_ch)

        
        
while True:
    Tile_map = []
    Loop_ch = []
    H, W = map(int,input().split())
    if H == 0 and W == 0:
        break
    for i in range(H):
        Tiles = input()
        Tiles = list(str(Tiles))
        Tile_map.append(Tiles)
    ans = move(Tile_map,0,0,Loop_ch)
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

N,M,L=map(int,input().split())
d=[[0 for i in range(0,N)] for i in range(0,N)]
for i in range(0,M):
    a,b,c=map(int,input().split())
    d[a-1][b-1]=c
    d[b-1][a-1]=c

csr1=csr_matrix(d)

a=floyd_warshall(csr1)

d=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    for j in range(0,N):
        if L>=a[i][j]:
            d[i][j]=1


csr2=csr_matrix(d)

data=floyd_warshall(csr2)
ans=[]
Q=int(input())
for i in range(0,Q):
    s,t=map(int,input().split())
    if data[s-1][t-1]!=float('inf'):
        ans.append(int(data[s-1][t-1])-1)
    else:
        ans.append(-1)

for i in range(Q):
    print(ans[i])
n=int(input())
s = list(input() for _ in range(n))
m=int(input())
t = list(input() for _ in range(m))

def list_difference(s,t):
    l = s.copy()
    for value in t:
        if value in l:
            l.remove(value)

    return l
l=list_difference(s,t)
print(l.most_common()[0][1])

### FIXED CODE ###

from collections import Counter
n=int(input())
s = [input() for _ in range(n)]
m=int(input())
t = [input() for _ in range(m)]

def list_difference(s,t):
    l = s.copy()
    for value in t:
        if value in l:
            l.remove(value)
    return l
l=list_difference(s,t)
l1=Counter(l)
if len(l)>0:print(l1.most_common()[0][1])
else:print(0)
N=int(input())
s=0
L=[i for i in range(N)]
A=list(map(int,input().split()))
dic1={i:i+a for i,a in zip(L,A)}
dic2={i:i-a for i,a in zip(L,A)}
for p in range(N)
    z=[k for k,v in dic1.items() if v==p ]
    w=[k for k,v in dic2.items() if v==p ]
    for i,j in zip(z,w):
        if j>i:
            s+=1
print(s)

### FIXED CODE ###

def count(dic,x):
    if x in dic:
        dic[x]+=1
    else:
        dic[x]=1

N=int(input())
A=list(map(int,input().split()))
dic1={}
dic2={}
s=0
for i in range(N):
    count(dic1,i-A[i])
    count(dic2,i+A[i])
for x in dic1:
    if x in dic2:
        s+=dic1[x]*dic2[x]
print(s)
s = str(n)
flag = 0
    # １文字ずつ数値化し配列にする。
array = list(map(int, s))
    # 合計値を返す
for i in array:
  if i == 7:
    flag = 1
if flag ==1:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
flag = 0
    # １文字ずつ数値化し配列にする。
array = list(map(int, s))
    # 合計値を返す
for i in array:
  if i == 7:
    flag = 1
if flag ==1:
  print("Yes")
else:
  print("No")
n = int(input())
s = [input() for i in range(n)]

s_unique   = []
s_cnt      = [0]*n
unique_num = 0
for i in range(n):
  # 新しい文字列の場合は配列に加える
  if (not(s[i] in s_unique)):
  	s_unique.append(s[i])
  else:
    s_cnt[s_unique.index(s[i])] += 1

# 最大カウントの要素で再構成
cnt_max = max(s_cnt)
s_max = []
for i in range(n):
  if (s_cnt[i] == cnt_max):
    s_max.append(s_unique[i])

s_max = sorted(s_max)
for s in s_max:
  print(s)

### FIXED CODE ###

a, b, c  = map(int, input().split())
abc = len(set([a, b, c]))

if ( abc == 2):
  print('Yes')
else:
  print('No')
N, M = [int(x) for x in input().split()]

ok = 0
ng = 0
ng_l = {}
end = set()

for _ in range(M):
    p, S = [x for x in input().split()]
    p = int(p)

    if not p in end:
        if S == 'AC':
            ok += 1
            ng += ng_l[p]
            end.add(p)
        else:
            if p in ng_l:
                ng_l[p] += 1
            else:
                ng_l[p] = 1

print('{} {}'.format(ok, ng))


### FIXED CODE ###

N, M = [int(x) for x in input().split()]

ok = 0
ng = 0
ng_l = {}
end = set()

for _ in range(M):
    p, S = [x for x in input().split()]
    p = int(p)

    if not p in end:
        if S == 'AC':
            ok += 1
            end.add(p)

            if p in ng_l:
                ng += ng_l[p]
        else:
            if p in ng_l:
                ng_l[p] += 1
            else:
                ng_l[p] = 1

print('{} {}'.format(ok, ng))
from fractions import gcd


def lcm(x, y):
    return int(x / gcd(x, y) * y)


def greatLCM(a):
    ans = lcm(a[0], a[1])
    p = 2
    while p < len(a):
        ans = lcm(ans, a[p])
        p += 1
    return ans


n = int(input())
arr = list(map(int, input().split()))
g = greatLCM(arr)
answer = 0
for i in arr:
    answer += g / i
    answer %= 1e9 + 7

print(int(answer))


### FIXED CODE ###

import fractions

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def solve():
    memo = A[0]
    for i in range(1, N):
        memo = lcm(memo, A[i])

    ans = 0
    for i in range(N):
        ans += memo // A[i]

    return ans % (10 ** 9 + 7)

print(solve())
n = int(input())
d = [int(input()) for i in range(n)]
p.sort()
print(len(set(p)))

### FIXED CODE ###

n = int(input())
d = [int(input()) for i in range(n)]
d.sort()
print(len(set(d)))
import math

N = int(input().strip())
grid = []
for i in range(N):
  array = list(map(int, input().strip().split(' ')))
  grid.append(array)

for i in grid:
  i.sort()
  print(i)
  a,b = [i[0],i[1]]
  if(a == b or a+1 == b):
    print(2*a-2)
  else:
    c = int(math.sqrt(a*b))
	if c == a*b: c-=1
    if(c*(c+1)>=a*b):
      print(2*c-2)
    else:
      print(2*c-1)


### FIXED CODE ###

import math

N = int(input().strip())
grid = []
for i in range(N):
	array = list(map(int, input().strip().split(' ')))
	grid.append(array)

for i in grid:
	i.sort()
	a,b = [i[0],i[1]]
	if(a == b or a+1 == b):
		print(2*a-2)
	else:
		c = int(math.sqrt(a*b))
		if c**2 == a*b:
			c-=1
		if(c*(c+1)>=a*b):
			print(2*c-2)
		else:
			print(2*c-1)
from sys import stdin
input = stdin.readline

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

maxpoint = 0
if b > n:
    for i in range(n+1):
        tmp = int((a * i) / b)  - a * int(i/b) 
        maxpoint = max(tmp,maxpoint)
else:
    for i in reversed(range(n+1)):
        tmp = int((a * i) / b)  - a * int(i/b) 
        if b > 1:
            if i % (b-1) == 0 :
                maxpoint = max(tmp,maxpoint)
                print(maxpoint) 
                exit()
        elif b == 1:
            print(0)
            exit()
        maxpoint = max(tmp,maxpoint)
        # print(maxpoint)

print(maxpoint)

### FIXED CODE ###


k = int(input())
a,b = map(int,input().split())

for i in range(a,b+1):
    if i % k == 0:
        print('OK')
        exit()
print('NG')
import numpy as np

N, M = map(int, input().split())

lr = [list(map(int, input().split())) for _ in range(M)]

mat = np.ones((M, N), dtype=np.int32)

for i, (l, r) in enumerate(lr):
    mat[i, 0:l-1] = 0
    mat[i, r:N] = 0

ans = mat[0,:]
    
for i in range(1, M):
    ans *= mat[i,:]

print(sum(ans))


### FIXED CODE ###

N, M = map(int, input().split())

lr = [list(map(int, input().split())) for _ in range(M)]

l_max = 1
r_min = N

for l, r in lr:
    l_max = max(l, l_max)
    r_min = min(r, r_min)

print(max(r_min - l_max + 1, 0))