Harryxun/stf_run huggingface dataset:
import numpy as np
def lcm(x,y):
    return int(x*y/np.gcd(x,y))
A,B,C,D=map(int,input().split())

S=B-A+1
if(A%C==0):
    n_C=B//C-A//C+1
else:
     n_C=B//C-A//C

if(A%D==0):
    n_D=B//D-A//D+1
else:
    n_D=B//D-A//D

if(A%lcm(C,D)==0):
    n_CD=B//lcm(C,D)-A//lcm(C,D)+1
else:
    n_CD=B//lcm(C,D)-A//lcm(C,D)
    
print(S-n_C-n_D+n_CD)

### FIXED CODE ###

def gcd(a,b):
    if(a<b):
        tmp=b
        b=a
        a=tmp
    while(a%b!=0):
        tmp_1=b
        tmp_2=a%b
        a=tmp_1
        b=tmp_2
    return b
    
def lcm(x,y):
    return int(x*y/gcd(x,y))

A,B,C,D=map(int,input().split())

S=B-A+1
if(A%C==0):
    n_C=B//C-A//C+1
else:
     n_C=B//C-A//C

if(A%D==0):
    n_D=B//D-A//D+1
else:
    n_D=B//D-A//D

if(A%lcm(C,D)==0):
    n_CD=B//lcm(C,D)-A//lcm(C,D)+1
else:
    n_CD=B//lcm(C,D)-A//lcm(C,D)
    
print(S-n_C-n_D+n_CD)
H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

memo = dict()

def ibis(H):
    if H in memo.keys():
        return memo[H]
    if H <= 0:
        return 0
    mp = []
    for n in range(N):
        mp.append(B[n] + ibis(H - A[n]))
    memo[H] = min(mp)
    return memo[H]

print(ibis(H))

### FIXED CODE ###

H, N = map(int, input().split())
x = [list(map(int, input().split())) for n in range(N)]
x = [[tmp[i] for tmp in x] for i in range(len(x[0]))]
A = x[0]
B = x[1]

def ibis(H, A, B):
    dp = [max(B) * H] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for n in range(N):
            hp = min(h + A[n], H)
            dp[hp] = min(dp[hp], dp[h] + B[n])
    return dp[H]

print(ibis(H, A, B))
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

if N==1:
    print(sum(anslis))
else:
    print(sum(anslis[0:N+1]))


### FIXED CODE ###

T, X = map(int, input().split())
print(T / X)
s = str(input())
k = str(input())
lis = []
ans = "zzz"
li = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for k in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+k] == "":
				continue
			if s[i:i+k] not in lis:
				lis.append(s[i:i+k])
		except:
			continue
lis.sort()

for i in range(k-1):
	lis.remove(lis[0])

print(lis[0])

### FIXED CODE ###

s = str(input())
k = int(input())
lis = []
for u in range(6):
	for i in range(len(s)):
		try:
			if s[i:i+u] == "":
				continue
			if s[i:i+u] not in lis:
				lis.append(s[i:i+u])
		except:
			continue
lis.sort()
print(lis[k-1])
n,k=map(int,input().split())
a=[]
for i in range(n):
  a.append(input())
b=sort.a
print(b(n-1)-b(n-k+1))

### FIXED CODE ###

n,k=map(int,input().split())
a=[]
for x in range(n):
  a.append(int(input()))
ans=1000000009
a=sorted(a)
for y in range(n-k+1):
  ans=min(a[y+k-1]-a[y],ans)
  
print(ans)
k = int(input())
s = input()

if len(s)<= k:
    print(S)
else:
    print(s[:k],"...")

### FIXED CODE ###

k = int(input())
s = input()

if len(s)<= k:
    print(s)
else:
    print(s[:k]+"...")
from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
warp = [[INF]*w for _ in range(h)]
ans=bfs(maze, warp, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)


### FIXED CODE ###

from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)
import math

n = int(input())

distans = []
tmps = []
for i in range n:
    x,y = map(int,input().split())
    tmps[i] = (x - y)**2

for i in range n-1:
    distans[i] = math.sqrt(tmps[i] + tmps[i+1])
    ans += distans[i] * (math.factorial(n)-1) 

print(ans/math.factorial(n))

### FIXED CODE ###

import itertools
import math
n = int(input())
xy = [list(map(int,input().split()))for _ in range(n)]

ans = 0
for i in itertools.permutations(range(n), n):
    tmp = i[0]
    for j in i:
        ans += (((xy[tmp][0]-xy[j][0])**2 + (xy[tmp][1]-xy[j][1])**2)**0.5)
        tmp = j
print(ans/math.factorial(n))
fa = [x for x in range (100002)]
ans = [-1 for i in range (100002)]
siz = [0 for i in range (100002)]

def find (x) : 
    fa[x] = x if fa[x] == x else find (fa[x])
    return fa[x]

def union (x, y) :
    fa[find (x)] = find (y)
    
N, M, K = list (map (int, input().split()))

for i in range (M) :
    a, b = list (map (int, input().split()))
    union (a, b)
    ans[a] -= 1
    ans[b] -= 1
    
for i in range (1, N + 1) :
    siz[find(i)] += 1

for i in range (1, N + 1) :
    ans[i] += siz[find (i)]

for i in range (K) :
    c, d = list (map (int, input().split()))
    if (find (c) == find (d)) :
        ans[c] -= 1
        ans[d] -= 1

print (' '.join (list (map(str , ans[1 : N + 1]))))


### FIXED CODE ###

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

fa = [x for x in range (n + 1)]
siz = [1 for i in range (n + 1)]
dep = [0 for i in range (n + 1)]
e = [1 for i in range (n + 1)]

def find (x) :
    if (fa[x] == x) :
        return x
    fa[x] = find (fa[x])
    return fa[x]

def uni (x, y) :
    u, v = find (x), find (y)
    if (dep[u] >= dep[v]) :
        fa[v] = u
        if (u != v) :
            siz[u] += siz[v]
        if (dep[u] == dep[v]) :
            dep[u] += 1
    else :
        fa[u] = v
        if (u != v) :
            siz[v] += siz[u]

for i in range (m) :
    a, b = list (map (int, input ().split ()))
    uni (a, b)
    e[a] += 1
    e[b] += 1

for i in range (1, n + 1) :
    siz[i] = siz[find (i)]

for i in range (k) :
    c, d = list (map (int, input ().split ()))
    if (find (c) == find (d)) :
        siz[c] -= 1
        siz[d] -= 1

siz = [siz[i] - e[i] for i in range (1, n + 1)]

print (' '.join (list (map (str, siz))))
N, M = map(int, input().split())
a=[]
for _ in range(M):
    a.append(int(input()))

lst=[0]*(N+1)
def func(n):
    if n in a:
        return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp

print(func(N))

### FIXED CODE ###

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

N, M = map(int, input().split())
a=[]
for _ in range(M):
    a.append(int(input()))

lst=[None]*(N+1)
def func(n):
    #if n in a:
    #    return 0
    if n<=1:
        return 1
    else:
        if lst[n]:
            return lst[n]
        else:
            temp=(func(n-1)+func(n-2))%(10**9+7)
            lst[n]=temp
            return temp



a=[-1]+a+[N+1]
answer=1
for i in range(M+1):
    if a[i+1]-a[i]==1:
        print(0)
        break
    answer=( func(a[i+1]-a[i]-2)*answer )%(10**9+7)
else:
    print(answer)
n,k = (int(x) for x in input().split())
town = [int(i) for i in input().split()]
warp  = [1]
checklist = [0]+[-1]*n
i = 0
j = 0
s = 0
while j<=n:
    warp.append(town[i])
    if checklist[town[i]-1]!=-1:
        s = checklist[town[i]-1]
        warp = warp[s:j]
        break
    checklist[town[i]-1] = j
    i = town[i]-1
    j += 1

m = len(warp)
print(warp[(k-s)%m])


### FIXED CODE ###

n,k = (int(x) for x in input().split())
town = [int(i) for i in input().split()]
warp  = [1]
checklist = [0]+[-1]*n
i = 0
j = 1
s = 0
while j<=n:
    warp.append(town[i])
    if checklist[town[i]-1]!=-1:
        s = checklist[town[i]-1]
        loop = warp[s:j]
        break
    checklist[town[i]-1] = j
    i = town[i]-1
    j += 1
if k>=s:
    m = len(loop)
    print(loop[(k-s)%m])
else:
    print(warp[k])
import sys

b={}
for s in sys.stdin:
    i = s[s.index(',')+1:-1]
    try:
        b[i]+=1
    except:
        b[i]=1
for e in [0,1,3,2]:
    print b[b.keys()[e]]

### FIXED CODE ###

import sys

b=[s.split(',')[1][:-1] for s in sys.stdin]
for e in ["A","B","AB","O"]:
    print b.count(e)
import bisect

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

# ある値以上のAiがいくつあるかの情報を累積和で保持
num_A_or_more = [0]*(10**5)
for a in A:
  num_A_or_more[a-1] += 1


for i in range(len(num_A_or_more)-1, 0, -1):
  num_A_or_more[i-1] += num_A_or_more[i]


# x以上となる手の組み合わせがM種類以上あるかどうかを判定
def check(x):
  count = 0
  for a in A:
    idx = max(x-a-1, 0)
    count += num_A_or_more[idx]
  
  return count>=M


# 2分探索でM種類以上の手の組み合わせがある満足度の最大値を求める
left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

# これがM種類以上の手の組み合わせがある満足度の最大値
x = left


# 降順に並べなおして累積和を求めておく
rev_A = A[::-1]
accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5 # M種類を超えた場合は、一番小さくなる握手の組を最後に削る
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)

### FIXED CODE ###

import bisect

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
rev_A = A[::-1]

def check(x, a=A, m=M):
  result = False
  n = len(a)
  count = 0
  for ai in a:
    count += (n - bisect.bisect_left(a, x-ai))
  
  return count>=m


left = 0
right = 2*10**5 + 1
mid = (left + right) // 2
while right - left > 1:
  if check(mid):
    left = mid
  else:
    right = mid
    
  mid = (left + right)//2

x = left
if check(right):
  x = right

accum_A = [rev_A[0]]
for i, a in enumerate(rev_A):
  if i == 0:
    continue
  accum_A.append(accum_A[-1] + a)

ans = 0
count = 0
surplus = 2*10**5
for ai in rev_A:
  idx = bisect.bisect_left(A, x-ai)
  if idx == N:
    break
  ans += (N-idx)*ai + accum_A[N-idx-1]
  count += N - idx
  surplus = min(surplus, ai+A[idx])


print(ans - (count-M)*surplus)
N=input().split()
p=map(int, input().split())
NN=int(N[0])
MM=int(N[1])
p2=[0.]*(NN-MM+1)
for i in range(NN-MM+1):
    a=0.
    for j in range(MM):
        a=a+(p[i+j]+1)/2
    p2[i]=a
print(max(p2))

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
for i in range(N-1):
    p[i+1]=p[i+1]+p[i]
max=p[K-1]
if N>K:
    for i in range(1,N-K+1):
        tmp=p[i+K-1]-p[i-1]
        if max < tmp:
            max=tmp
print((max+K)/2.)
s=input()
t=input()
cnt=0
for i in range(3):
  if s[i]=t[i]:
    cnt+=1
print(cnt)

### FIXED CODE ###

s=input()
t=input()
cnt=0
for i in range(3):
  if s[i]==t[i]:
    cnt+=1
print(cnt)
import math
import sys
N = int(input())
s = input()
k = int(input())
t = s[k-1]
u = ""
for i in s:
    if s[i] == t:
        u += s[i]
    else :
        u += '*'
print(u)



### FIXED CODE ###

import math
import sys
N = int(input())
s = input()
k = int(input())
t = s[k-1]
u = ""
for i in s:
    if i == t:
        u += i
    else :
        u += '*'
print(u)
N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007

C = [3] + [0 for i in range(N)]

ans = 1
for a in A:
  ans *= C[a]
  ans %= MOD
  C[a] -= 1
  C[a+1] += 1
print(ans)

### FIXED CODE ###

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

C = [3] + [0 for i in range(N)]

ans = 1
for a in A:
  ans *= C[a]
  ans %= MOD
  C[a] -= 1
  C[a+1] += 1
print(ans)
nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*(10**5)
for loop in range(len(liste)):
  liste2[liste[loop]] = liste.count(liste[loop])
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  for loop in range(len(liste)):
    if liste[loop]==n:
      liste[loop] = r
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)


### FIXED CODE ###

nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*((10**5)+1)
for loop in range(len(liste)):
  liste2[liste[loop]] +=1
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)
a=int(input())

if a%2 == 0:
  print(-1)
else:
  ans = 1
  div = 0
  
  for i in range(10**6):
    div += 7*10**i
    if a%div == 0:
      break
    else:
      ans +=1

print(ans)

### FIXED CODE ###

k = int(input())
a = 0
for i in range(k):
  a = (a*10+7)%k
  if a == 0:
    print(i+1)
    quit()
print(-1)
H, W = map( int, input().split())

a = []
b = []
c = []

for i in range(H):
  a1 = input()
  if('#' in a1):
     a.append(a1)
        
  else:
      continue

a = list(zip(*a))
l1 = len(a)
         
for j in range(l1):
  b1 = a[j]
   
  if( '#' in b1):
      b.append(b1)
  
  else:
      continue
         
c = list(zip(*b))
l2 = len(c)

for n in range(l2):
         print("".join(c[n]))

### FIXED CODE ###

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

print(N - i + 1)
N = int(input())
h = list(map(int,input().split()))
h.append(0)

count=0
while 1:
	flag=0
    for i in range(N):
    	if h[i]>0:
        	h[i] -= 1
      	    flag = 1
        if h[i+1] == 0:
        	count += 1
        else:
        	pass
    if flag == 0:
    	break
print(count)

### FIXED CODE ###

N,K=list(map(int,input().split()))
h=[]
for i in range(N):
  h.append(int(input()))
h.sort()

minimum=1000000000
for j in range(N-K+1):
  minimum=min(minimum, h[j+K-1]-h[j])
print(minimum)
import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    if N > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        divs = set()
        digit = 1
        factor = 0
        x = a
        for k, p in enumerate(primes):
            if x % p == 0:
                factor += digit
                x //= p

            while x % p == 0:
                x //= p
            digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            if x > 1:
                common_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()


### FIXED CODE ###

import math

def main():
    N = int(input())
    As = list(map(int, input().split()))
    pairwise_flag = True
    setwise_flag = True
    cnt_not1 = 0
    for a in As:
        if a > 1:
            cnt_not1 += 1
    if cnt_not1 > 78498:
        pairwise_flag = False
    
    L = 1000 + 1
    isPrime = [True] * L
    isPrime[0] = isPrime[1] = False
    primes = []
    for n in range(2, L):
        if isPrime[n]:
            primes.append(n)
            isPrime[2*n::n] = [False] * ((L-n-1) // n)

    or_factor = 0
    or_factor_over1000 = set()
    all_gcd = None
    for i, a in enumerate(As):
        digit = 1
        factor = 0
        x = a
        if pairwise_flag:
            for p in primes:
                if p > x:
                    break
                if x % p == 0:
                    factor += digit
                    x //= p

                while x % p == 0:
                    x //= p
                digit <<= 1

        if i > 0:
            all_gcd = math.gcd(all_gcd, a)
            if pairwise_flag:
                if or_factor & factor:
                    pairwise_flag = False
                or_factor |= factor
                if x > 1:
                    if x in or_factor_over1000:
                        pairwise_flag = False
                    or_factor_over1000.add(x)
        else:
            all_gcd = a
            or_factor |= factor
            if x > 1:
                or_factor_over1000.add(x)
    if pairwise_flag:
        print('pairwise coprime')
    elif all_gcd > 1:
        print('not coprime')
    else:
        print('setwise coprime')

main()
import math

A,B,K = map(int,input().split(" "))
GCA = math.gcd(A, B)
all_div=[]

C = min(A,B)

for i in range(1,C+1):
    if C % i == 0:
        if i <= GCA:
            all_div.append(i)
all_div.sort(reverse=True)
print(all_div[K-1])

### FIXED CODE ###

A,B,K = map(int,input().split(" "))

def gcd(a, b):
	while b:
		a, b = b, a % b
	return int(a)

GCA = gcd(A, B)
A_all_div=[]
B_all_div=[]


for i in range(1,A+1):
    if A % i == 0:
        if i <= GCA:
            A_all_div.append(i)
A_all_div.sort(reverse=True)

for i in range(1,B+1):
    if B % i == 0:
        if i <= GCA:
            B_all_div.append(i)
B_all_div.sort(reverse=True)

ALL_DIV = set(A_all_div) & set(B_all_div)
all_div = list(ALL_DIV)

all_div.sort(reverse=True)

print(all_div[K-1])
n, m = map(int, input().split())
d = dict()
for i in range(m):
    s, c = map(int, input().split())
    if s==1 and c==0:
        print("-1")
        exit()
    if s in d.keys() and d[s] != c:
        print("-1")
        exit()
    d[s] = c
if d[2] == 0 and 1 not in d.keys():
    print("-1")
    exit()
target = 0
for s, c in d.items():
    target += 10**(n-s)*c
print(target)

### FIXED CODE ###

n, m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(m)]
if n == 1:
    for i in range(10):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
else:
    for i in range(10**(n-1),10**n):
        tmp = str(i)
        flag = True
        for j in range(m):
            if tmp[arr[j][0]-1] != str(arr[j][1]):
                flag = False
        if flag:
            print(i)
            exit()
    print(-1)
A,B,K = map(int,input().split())

C=[]
for i in range(1,A):
  if A%i==0 and B%i==0:
    C.append(i)

#print(C)
print(C[-K])
  

### FIXED CODE ###

A,B,K = map(int,input().split())

C=[]
for i in range(1,101):
  if A%i==0 and B%i==0:
    C.append(i)

#print(A,B,K)
#print(C)
print(C[-K])
S = input()
T = input()
LS = len(S)
LT = len(T)
L = []

if T in S:
  print(0)
else:
    for ls in range(LS - LT):
        d = 0
        for lt in range(LT):
            if S[ls + lt:ls + LT] != T[lt]:
                d += 1
        L.append(d)
    print(min(L))

### FIXED CODE ###

S = input()
T = input()
LS = len(S)
LT = len(T)
L = []

if T in S:
  print(0)
else:
    for ls in range(LS - LT + 1):
        d = 0
        for lt in range(LT):
            if S[ls + lt] != T[lt]:
                d += 1
        L.append(d)
    print(min(L))
import numpy as np
N = int(input())
A = list(map(int,input().split())) #準備度
B = list(map(int,input().split())) #試験

A = np.array(A)
B = np.array(B)


sumA = sum(A)
sumB = sum(B)

if sumA < sumB:
    print(-1)
else:
    gap = A - B
    minus = gap[gap<0]
    numminus = len(gap[gap<0])
    if numminus == 0:
        print(0)
    else:
        needs = - minus.sum()
        sortgap = np.sort(gap)[::-1]
        s = 0
        for i in range(N):
            s += sortgap[i]
            if s >= needs:
                changedplus = i+1
                break
        print(changedplus + numminus)

### FIXED CODE ###

nums = list(map(int,input().split()))
flag1 = 1 in nums and 9 in nums and 7 in nums and 4 in nums
if flag1 == True:
    print("YES")
else:
    print("NO")
def main():

    N, M = map(int, input().split())
    if N == 1:
        s, c = map(int, input().split())
        if s == 1: return c
        else: return -1

    if M == 0:
        return pow(10, N-1)

    sc = []
    for _ in range(M):
        s, c = map(int, input().split())
        sc.append([s, c])

    for v in range(pow(10, N-1), pow(10, N)):
        t = str(v)
        if all(t[s-1] == str(c) for s, c in sc):
            return v
    return -1

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

### FIXED CODE ###

def main():

    N, M = map(int, input().split())
    sc = []
    for _ in range(M):
        s, c = map(int, input().split())
        sc.append([s, c])

    start = pow(10, N-1)
    if N == 1: start = 0
    
    for v in range(start, pow(10, N)):
        t = str(v)
        if all(t[s-1] == str(c) for s, c in sc):
            return v
    return -1

if __name__ == '__main__':
    print(main())
has_seven = False
N = str(input())
for i in range(len(N)):
  	if N[i] == '7':
    	has_seven = True
    	break

if has_seven:
	print("Yes")
else:
	print("No")




### FIXED CODE ###


has_seven = False
N = str(input())
for i in range(len(N)):
  if N[i] == '7':
      has_seven = True
      break

if has_seven:
  print("Yes")
else:
  print("No")
n, m = map(int, input().split())
l = list(map(int, input().split()))

l.sort()
distance = []
sum = 0

if m == 1:
    print("0")
    exit()

for i in range(len(l) - 1):
    distance.append(l[i+1] - l[i])

distance.sort(reverse=True)

for i in range(n-1):
    sum += distance[i]

print(l[len(l)-1] - l[0] - sum)


### FIXED CODE ###

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

l.sort()
d = l[len(l)-1] - l[0]
distance = []
sum = 0

for j in range(len(l)-1):
    distance.append( l[j+1] - l[j] )

distance.sort(reverse=True)

if n >= m:
    print("0")
else:
    for i in range(n-1):
        sum += distance[i]
    print(d-sum)