Harryxun/stf_run huggingface dataset:
n,m= map(int,input().split())
henl = []
usehen = [False] * n
brdic = {}
for _ in range(m):
    a,b= map(int,input().split())
    brdic[a] = brdic.get(a,[]) + [b]
    brdic[b] = brdic.get(b,[]) + [a]
    henl.append((a,b))

ordin = [-1]*(n+1)
lowlink = [-1]*(n+1)
k=[1]
bn=[0]
def dfs(node):
    ordin[node]=k[0]
    k[0]+=1
    lowlink[node]=ordin[node]
    for br in brdic[node]:
        temp = (min(node,br),max(node,br))
        if ordin[br]==-1:
            usehen[henl.index(temp)]=True
            dfs(br)
            lowlink[node] = min(lowlink[br],lowlink[node])
        else:
            if usehen[henl.index(temp)]==False:lowlink[node] = min(ordin[br],lowlink[node])
        if ordin[node] < lowlink[br]:bn[0]+=1
dfs(1)
print(bn[0])

### FIXED CODE ###

n,m= map(int,input().split())
henl = []
usehen = [False] * m
brdic = {}
for _ in range(m):
    a,b= map(int,input().split())
    brdic[a] = brdic.get(a,[]) + [b]
    brdic[b] = brdic.get(b,[]) + [a]
    henl.append((a,b))

ordin = [-1]*(n+1)
lowlink = [-1]*(n+1)
k=[1]
bn=[0]
def dfs(node):
    ordin[node]=k[0]
    k[0]+=1
    lowlink[node]=ordin[node]
    for br in brdic[node]:
        temp = (min(node,br),max(node,br))
        if ordin[br]==-1:
            usehen[henl.index(temp)]=True
            dfs(br)
            lowlink[node] = min(lowlink[br],lowlink[node])
        else:
            if usehen[henl.index(temp)]==False:lowlink[node] = min(ordin[br],lowlink[node])
        if ordin[node] < lowlink[br]:bn[0]+=1
dfs(1)
print(bn[0])
n = input()
A = map(int, input().split())
q = input()
m = map(int, input().split())

def solve(i, m):
 if i == m:
  return true
 if i > n:
  return false
 res = solve(i + 1, m) || solve(i + 1, m - A[i])
  return res
 
 for j in range(0, q-1):
  if m == solve(j, m(j)):
   print "yes"
  else:
   print "no"

### FIXED CODE ###

n = input()
A = map(int, raw_input().split())
q = input()
m = map(int, raw_input().split())

def solve(i, m):
 if m == 0:
  return True
 if i >= n or m > sum(A):
  return False
 res = solve(i+1, m) or solve(i+1, m-A[i])
 return res

for j in range(0, q):
 if solve(0, m[j]):
  print 'yes'
 else:
  print 'no'
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
x0=0
x1=max(a)
while(1):
    sum=0
    mid=(x0+x1)//2
    for i in range(n):
        sum+=math.ceil(a[i]/mid)-1
    if(sum<=k):
        x1=mid
    if(sum>k):
        x0=mid
    if(x0+1==x1):
        print(x1)
        break

### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
x0=0
x1=10**9
while(1):
    sum=0
    mid=(x0+x1)//2
    for i in range(n):
        sum+=math.ceil(a[i]/mid)-1
    if(sum<=k):
        x1=mid
    if(sum>k):
        x0=mid
    if(x0+1==x1):
        print(x1)
        break
input = input()
sn = list(str(input))
y = 0
for i in sn:
  x = int(i)
  y = y + x

if input%%y == 0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

a = input()
sn = list(str(a))
y=0
 
for i in sn:
    x = int(i)
    y = y +x

a = int(a)
if a%y == 0:
    print('Yes')
else:
    print('No')
# Problem C - Tsundoku

# input
N, M, K = map(int, input().split())
a_nums = list(map(int, input().split()))
b_nums = list(map(int, input().split()))

# initialization
a_start = -1
b_start = -1
max_count = 0
cur_count = 0

# dfs search
def dfs(a_i, b_i):
    global max_count
    global cur_count
    global K

    if a_i>=N or b_i>=M:
        if cur_count>max_count:
            max_count = cur_count
        return

    # right check
    if a_i+1<N:
        if K - a_nums[a_i+1]>=0:
            K -= a_nums[a_i + 1]
            cur_count += 1
            dfs(a_i+1, b_i)
            cur_count -= 1
            K += a_nums[a_i + 1]
        else:
            if cur_count>max_count:
                max_count = cur_count
    else:
        if cur_count>max_count:
            max_count = cur_count

    # left check
    if b_i + 1<M:
        if K - b_nums[b_i + 1]>=0:
            K -=b_nums[b_i + 1]
            cur_count += 1
            dfs(a_i, b_i+1)
            cur_count -= 1
            K += b_nums[b_i + 1]
        else:
            if cur_count>max_count:
                max_count = cur_count
    else:
        if cur_count>max_count:
            max_count = cur_count

dfs(a_start, b_start)

# output
print(max_count)


### FIXED CODE ###

# Problem C - Tsundoku

# input
N, M, K = map(int, input().split())
a_nums = list(map(int, input().split()))
b_nums = list(map(int, input().split()))

# initialization
max_count = 0
b_i = M
a_cums = [0]*(N+1)
b_cums = [0]*(M+1)
for i in range(1, N+1):
    if i>1:
        a_cums[i] = a_cums[i-1] + a_nums[i-1]
    else:
        a_cums[i] = a_nums[i-1]
for i in range(1, M+1):
    if i>1:
        b_cums[i] = b_cums[i-1] + b_nums[i-1]
    else:
        b_cums[i] = b_nums[i-1]

for i in range(N+1):
    if a_cums[i]<=K:
        while b_i>0 and a_cums[i]+b_cums[b_i]>K:
            b_i -= 1
        if i+b_i>max_count:
            max_count = i+b_i

# output
print(max_count)
from math import gcd
n=int(input())
l=list(map(int,input().split()))
b=0
c=0
for i in range(n):
    if (i==0):
        b=l[i]
    else:
        b=b*l[i]//gcd(l[i],b)
for i in range(n):
    c+=b//l[i]
print(c%1000000007)


### FIXED CODE ###

import fractions
n=int(input())
l=list(map(int,input().split()))
b=0
c=0
for i in range(n):
    if (i==0):
        b=l[i]
    else:
        b=b*l[i]//fractions.gcd(l[i],b)
for i in range(n):
    c+=b//l[i]
print(c%1000000007)
import functools
import math
def slcm(numbers):
	return functools.reduce((lambda x,y:x*y//math.gcd(x, y)), numbers)
	
input()
numbers=list(map(int,input().split()))
num=slcm(numbers)-1
nums=[num%i for i in numbers]
print(sum(nums))


### FIXED CODE ###

import functools
import fractions

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

def slcm(numbers):
	return functools.reduce(blcm, numbers)
	
input()
numbers=list(map(int, input().split()))
num=slcm(numbers)-1
nums=[num%i for i in numbers]
print(sum(nums))
s = list(input())

t = list("AKIHABARA")

if len(s) > len(t):
    print("NO")
    exit()
    
if len(s) < 5:
    print("NO")
    exit()

while True:
    cnt = 0
    for i in range(8):
        if s[cnt] == t[i]:
            cnt += 1
            continue
        elif t[i] == "A":
            s.insert(i, "A")
            break
        else:
            print("NO")
            exit()
    else:
        break
        
print("YES")

### FIXED CODE ###

s = input()

check = ["KIHBR","KIHBRA","KIHBAR","KIHBARA","KIHABR","KIHABRA","KIHABAR","KIHABARA","AKIHBR","AKIHBRA","AKIHBAR","AKIHBARA","AKIHABR","AKIHABRA","AKIHABAR","AKIHABARA"]

if s in check:
    print("YES")
else:
    print("NO")
x, n = input().split()
x = int(x)
n = int(n)

if n==0:
	print(x)
else:
	p = list(map(int, input().split()))

	ans = -1
	mn = 10000

	for i in range(1, 101):
		if(p.count(i) == 0):
			d = x - i
			if d<0:
				d = -d
			if d<mn:
				ans = i
				mn = d
	if d == 10000:
		if(x <= 50):
			ans = 0
		else:
			ans = 101
	print(ans)

### FIXED CODE ###

x, n = input().split()
x = int(x)
n = int(n)

if n==0:
	print(x)
else:
	p = list(map(int, input().split()))

	ans = -1
	mn = 10000

	for i in range(-1, 102):
		if(p.count(i) == 0):
			d = x - i
			if d<0:
				d = -d
			if d<mn:
				ans = i
				mn = d
	print(ans)
class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        pa = uf.find(a)
        pb = uf.find(b)
        ans -= uf.size[pa] * uf.size[pb]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x]) # contraction
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if not self.same(x, y):
            self.size[y] += self.size[x]
        self.par[x] = y

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

uf = UnionFind(n)
ans = n * (n-1) // 2
anss = []
for i in reversed(range(m)):
    anss.append(ans)
    # print(uf.par)
    # print(uf.size, [uf.size[uf.find(i)] for i in range(n)])
    a, b = edge[i]
    if not uf.same(a, b):
        ans -= uf.size[uf.find(a)] * uf.size[uf.find(b)]
    # print(i, a, b)

    uf.unite(a, b)

for i in reversed(range(m)):
    print(anss[i])
N_M = list(map(int, input().split()))
N = N_M[0]
M = N_M[1]
for i in range(M):
    dis[i] = list(int(input()))

dp = [0 for i in range(N+2)]
dp[0] = 1
if 1 in dis:
    dp[1] = 0
else :
    dp[1] = 1

for i in range(N):
    if i+2 in dis:
        dp[i+2]=0
    else:
        if i in dis :
            dp[i+2]=dp[i+1]
        if i+1 in dis :
            dp[i+2]=dp[i]
        else :
            dp[i+2]=dp[i]+dp[i+1]

print(dp[N])

### FIXED CODE ###

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


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = 1
        else:
            dp[i] = 1
    else:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] = dp[i] % 1000000007
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

roots = []

# どのマスから始めるか
for i in range(1, N + 1):
    root = [i]
    visit = [False] * N
    visit[i - 1] = True
    now = i
    for j in range(K):
        next = P[now - 1]
        if visit[next - 1] == True:
            root.append(next)
            break
        else:
            visit[next - 1] = True
            root.append(next)
            now = next
    roots.append(root)
print(roots)

ans = 0
for root in roots:
    head = root[-1]
    head_idx = root.index(head)
    tail = root[-2]
    tail_idx = root.index(tail)
    roop_l = tail_idx - head_idx + 1
    roop = []
    for i in range(head_idx, tail_idx + 1):
        roop.append(root[i])
    # print(roop,"roop")
    if roop == []:
        cumsum = [0]
        for i in range(1, len(root)):
            cumsum.append(cumsum[-1] + C[root[i] - 1])
        # print(cumsum,"cumsum")
        m = max(cumsum)
        # print(m)
        ans = max(ans, m)
    else:
        cumsum = [0]
        for item in roop:
            cumsum.append(cumsum[-1]+C[item-1])
        m = max(cumsum)
        max_idx = cumsum.index(m)
        # print(cumsum,"else",max_idx)
        #
        cumsum2 = [0]
        for i in range(1,len(root)-1):
            cumsum2.append(cumsum2[-1]+C[root[i]-1])
        # print(cumsum2)
        if cumsum[-1]<=0:
            for item in root:
                cumsum2.append(cumsum[-1]+C[item-1])
            ans = max(cumsum2)
        else:
            K -= len(cumsum2)
            roop_cnt = K//len(roop)
            cumsum2.append(cumsum2[-1]+ cumsum[-1]*roop_cnt + m)
            ans = max(cumsum2)
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

# Pが1,2,...Nの順列なので、1,2,3,4,5,3,4,5,...のような途中からのループは起こり得ない
# スタートの点数が入らないのは面倒なので、スタートの次のマスから考える

ans = -(10**9)
# どのマスから始めるか
for i in range(1, N + 1):
    # ループに入るまでの経路(iの次から)
    route = []
    visit = [False] * (N + 1)
    visit[i] = True
    now = i
    while True:
        next = P[now]
        # まだ訪れていないマスの場合
        if visit[next] == False:
            visit[next] = True
            route.append(next)
            now = next
        # 既に訪れたマスの場合
        else:
            break
    # iに戻ってくる
    route.append(i)

    cumsum = [0]
    for x in route:
        cumsum.append(cumsum[-1] + C[x])
    # print(cumsum)

    # ループするほど損する場合
    if cumsum[-1] <= 0:
        if K >= len(route):
            tmp = max(cumsum[1:])
        else:
            tmp = max(cumsum[1:K + 1])
        ans = max(ans, tmp)
    # ループするほど得する場合
    else:
        loop_size = len(route)
        loop_cnt = K // loop_size
        spare_cnt = K % loop_size
        # (loop_cnt -1)回ループしたところから
        cumsum2 = [cumsum[-1] * (loop_cnt - 1)]
        for x in route:
            cumsum2.append(cumsum2[-1] + C[x])
        for x in route[:spare_cnt]:
            cumsum2.append(cumsum2[-1] + C[x])
        tmp = max(cumsum2[1:])
        ans = max(ans, tmp)

print(ans)
a, b, c = [0] * 3
x = []

def format_input(filename = None):
	global a, b, c
	global x
	if filename == None:
		a, b, c = list(map(int, input().split()))
		x = [list(map(int, input().split())) for i in range(n)]

	elif filename == '__random__'
		from random import randint as rng
		a = rng(1, 10**1)
		b = rng(1, 10**1)
		c = rng(1, 10**1)
		x = [[rng(1, 10**1), rng(1, 10**1)] for i in range(n)]

def get_answer(a, b, c, x):
	answer = 0
	return answer

if __name__ == '__main__':
	format_input('__random__')

	ans = get_answer(a, b, c, x)
	print(ans)


### FIXED CODE ###



s, t= [""] * 2
a, b = [0] * 2
u = [""]

def format_input(filename = None):
	global s,t
	global a,b
	global u
	if filename == None:
		s, t = list(map(str, input().split()))
		a, b = list(map(int, input().split()))
		u = list(map(str, input().split())).pop()

def get_answer():
	answer = [a, b]
	if u == s:
		answer[0] -= 1
	else:
		answer[1] -= 1

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans[0], ans[1])
from collections import deque


ans = {1:1}

def dfs(tree,nodes):
    for node in nodes:
        nexts = tree[node]
        for next,l in nexts.items():
            if l% 2 == 0 :
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
        if len(ans) == N:
            return
        dfs(tree,nexts)

    return 0




if __name__ == "__main__":
    tree= {}
    N = int(input())
    for i in range(N-1):
        u,v,w = list(map(int,input().split(" ")))

        if u not in tree:
            tree[u] = {}
        tree[u][v] = w

        if v not in tree:
            tree[v] = {}
        tree[v][u] = w

    dfs(tree,[1])
    for i in range(1,N+1):
        print(ans[i])


### FIXED CODE ###

from collections import deque
import sys

sys.setrecursionlimit(50000000)


ans = {1: 1}


def dfs(tree, nodes):
    for node in nodes:
        nexts = tree[node]
        for next, l in nexts.items():
            if l % 2 == 0:
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree, nexts)

    return 0


if __name__ == "__main__":
    tree = {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w % 2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N - 1):
            u, v, w = list(map(int, input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
        dfs(tree, [1])
        for i in range(1, N + 1):
            print(ans[i])
n,k=map(int,input().split())

a=[]
b=[]
d={}
for _ in range(n):
    a_i,b_i=map(int,input().split())
    d[a_i]=b_i

d=sorted(d.items(),key=lambda x: x[0])


prev=0
for key,value in d:
    a.append(key)
    b.append(prev+value)

    prev+=value


for j in range(n):
    if k<=b[j]:
        break

print(a[j])


### FIXED CODE ###

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

d={}
for _ in range(n):
    a_i,b_i=map(int,input().split())
    if a_i in d:
        d[a_i]+=b_i
    else:
        d[a_i]=b_i


a=[]
b=[]

d=sorted(d.items(),key=lambda x: x[0])


prev=0
for key,value in d:
    a.append(key)
    b.append(prev+value)

    prev+=value


for j in range(len(b)):
    if k<=b[j]:
        break

print(a[j])
#最小公倍数でループ
import math
n = int(input())
ans = list(map(int,input().split()))
lcm = ans[0]
for k in ans:
    gcd = math.gcd(lcm, k)
    lcm = round(lcm*k/gcd)
    print(lcm)


an =0
for k in ans:
    an += (lcm-1)%k
        
print(an)

### FIXED CODE ###

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

print(sum(ans)-n)
N = int(input())
S = []
C0 = 0
C1 = 0
C2 = 0
C3 = 0

for i in range(N-1):
    S = input()
    if S == AC:
        C0 = C0 + 1
    elif S == WA:
        C1 = C1 + 1
    elif S == TLE:
        C2 = C2 + 1
    else:
        C3 = C3 + 1

print("AC x " + C0)
print("WA x " + C1)
print("TLE x " + C2)
print("RE x " + C3)



### FIXED CODE ###

N = int(input())
C0, C1, C2, C3 = 0, 0, 0, 0

for i in range(N):
    S = str(input())
    if S == "AC":
        C0 = C0 + 1
    elif S == "WA":
        C1 = C1 + 1
    elif S == "TLE":
        C2 = C2 + 1
    else:
        C3 = C3 + 1

print("AC x " + str(C0))
print("WA x " + str(C1))
print("TLE x " + str(C2))
print("RE x " + str(C3))
N = int(input())

N = int(N[-1])

if N == 0 or N == 1  or N == 6  or N == 8 :
    print("pon")
elif N == 3:
    print("bon")
else:
    print("hon")

### FIXED CODE ###

N = input()

N = int(N[-1])

if N == 0 or N == 1  or N == 6  or N == 8 :
    print("pon")
elif N == 3:
    print("bon")
else:
    print("hon")
k =int(input())
a, b = map(int, input().split())

for i in range(a, b):
    if (i % k == 0):
        break
    
if(i%k==0):
    print("OK")
else:
    print("NG")

### FIXED CODE ###

k =int(input())
a, b = map(int, input().split())
 
for i in range(a, b+1):
    if (i % k == 0):
        print("OK")
        break
else:
    print("NG")
N=int(input())
d=[input() for i in range(N)]
s=0
for i in range(0,len(d)):
  t=0
  for j in range(0,len(d)):
    t+=d[i]*d[j]
  s+=t
print(s)

### FIXED CODE ###

N=int(input().rstrip())
d = list(map(int, input().split())) 
a=0
t=0
for i in range(N-1):
  t+=1
  for j in range(t,N):
    a+=d[i]*d[j]
print(a)
n = int(input())
x_list = list(map(int,input().split()))
#print(x_list)
#print(sum(x_list))
#(len(x_list))

#p = sum(x_list) // (len(x_list))
#p = (min(x_list) + max(x_list)) // 2
#print(p)

ans_list = [0] * (max(x_list)+1)

for j in range(1, max(x_list)+1):
    ans = 0
    for i in range(0, n):
        ans += (x_list[i] - j) ** 2
        #print(ans)
    ans_list[j] = ans

ans_list.remove(0)
print(min(ans_list))
#print(ans)n = int(input())
x_list = list(map(int,input().split()))
#print(x_list)
#print(sum(x_list))
#(len(x_list))

#p = sum(x_list) // (len(x_list))
#p = (min(x_list) + max(x_list)) // 2
#print(p)

ans_list = [0] * (max(x_list)+1)

for j in range(1, max(x_list)+1):
    ans = 0
    for i in range(0, n):
        ans += (x_list[i] - j) ** 2
        #print(ans)
    ans_list[j] = ans

ans_list.remove(0)
print(min(ans_list))
#print(ans)

### FIXED CODE ###

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

ans_list = [0] * (max(x_list)+1)

for j in range(1, max(x_list)+1):
    ans = 0
    for i in range(0, n):
        ans += (x_list[i] - j) ** 2
    ans_list[j] = ans

ans_list.remove(0)
print(min(ans_list))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):

        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]


N, M = map(int, input().split()) 
union_find = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    union_find.union(A, B)

answer = 0
for i in range(N):
    answer = max(answer, union_find.size(i))

print(answer)

### FIXED CODE ###

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

root = [-1]*n
def r(x):
    if root[x] < 0:
        return x
    else:
        root[x] = r(root[x])
        return root[x]

def unite(x, y):
    x = r(x)
    y = r(y)
    if x == y:
        return
    root[x] += root[y]
    root[y] = x

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, -root[i])

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

ans = []
for i in range(1, max(a,b)):
  if a % i == 0 and b % i == 0:
    ans.append(i)
    
print(ans[len(ans)- k])
  

### FIXED CODE ###

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

ans = []
for i in range(1, max(a,b)+1):
  if a % i == 0 and b % i == 0:
    ans.append(i)
print(ans[len(ans)- k])
ans = 0
for i in range(L, R):
  if i % d == 0:
    ans += 1
return ans

### FIXED CODE ###

L, R, d = map(int, input().split())
 
count = 0
for i in range(L, R+1):
    if i % d == 0:
        count+=1
 
print(count)
import sys
sys.setrecursionlimit(100000)

N, A, B = map(int, input().split())
mo = 10 ** 9 + 7
def hanaya(n, x):
    if x == 1:
        return n
    else:
        return ((hanaya(n, x-1))*((n-x+1)/x))%mo
    
ans = (pow(2, N, mo) - 1 - hanaya(N, A)- hanaya(N, B)) % mo
print(int(ans))

### FIXED CODE ###

N, A, B = map(int, input().split())
mo = 1000000007
A_val = 1
for i in range(A):
    A_val = ((A_val * (N - i) * pow(i+1, mo-2, mo))) % mo
B_val = 1
for i in range(B):
    B_val = ((B_val * (N - i) * pow(i+1, mo-2, mo))) % mo
    
ans = (pow(2, N, mo) - 1 - A_val - B_val) % mo
print(ans)
S = list(input())

firstS = S[:len(S) // 2]
secondS = list(reversed(S[len(S) // 2 + 1:]))

count = 0

for x in range(len(firstS)):
    if firstS[x] != secondS[x]:
        count += 1
print(count)


### FIXED CODE ###

S = list(input())

firstS = S[:len(S) // 2]
if len(S) % 2 == 0:
    secondS = list(reversed(S[len(S) // 2:]))
else:
    secondS = list(reversed(S[len(S) // 2 + 1:]))

count = 0

for x in range(len(firstS)):
    if firstS[x] != secondS[x]:
        count += 1
print(count)
n = sorted(list(map(int,input().split())))
print(int(n[0]*n[1]/2))

### FIXED CODE ###

s = input()
print(s[0]+str(len(s)-2)+s[-1])
N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
# print(N, xyh)

height = None
found = False
for cx in range(0, 101):
    for cy in range(0, 101):
        height = abs(xyh[0][0] - cx) + abs(xyh[0][1] - cy) + xyh[0][2]
        foo = [(abs(x - cx) + abs(y - cy) + h == height or (abs(x - cx) + abs(y - cy) + h == 0) for x, y, h in xyh]
        found = all(foo)
        if found: break
    if found: break
print(cx, cy, height)


### FIXED CODE ###

N = int(input())
xyh = [list(map(int, input().split())) for i in range(N)]
# print(N, xyh)

height = None
found = False
for cx in range(0, 101):
    for cy in range(0, 101):
        candidate = 0
        for x, y, h in xyh:
            if h == 0: continue
            dx = abs(x - cx)
            dy = abs(y - cy)
            candidate = dx + dy + h 
            break

        found = True
        for x, y, h in xyh:
            _h = candidate - abs(x - cx) - abs(y - cy)
            if h == 0 and _h <= 0: continue
            if not h == _h:
                found = False
                break
        
        if found is True: break
    if found is True: break
height = candidate if candidate is not None else 0

print(cx, cy, height)