Harryxun/stf_run huggingface dataset:
import queue


# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]


# bfs algorithm
def bfs(h, w, cheese, maps, sx, sy, moves, visited):
    que = queue.Queue()
    que.put((moves, sx, sy))

    for i in range(h):
        for j in range(w):
            visited[i][j] = True

    visited[sy][sx] = False

    while que.qsize() > 0:
        c_moves, c_x, c_y = que.get()
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x] and maps[n_y][n_x] != 'X'):
                que.put((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)


# simulate mouse
def simulate(h, w, n, maps, sx, sy):
    moves = 0
    x, y = sx, sy

    visited = [[True for i in range(w)] for j in range(h)]

    for i in range(1, n+1, 1):
        moves, x, y = bfs(h, w, str(i), maps, x, y, moves, visited)

    return str(moves)


# main function
def main():
    str = (input()).split()

    H = int(str[0])
    W = int(str[1])
    N = int(str[2])

    maps = []
    sx, sy = 0, 0
    for i in range(H):
        maps.append(input())
        for j in range(W):
            if maps[i][j] == 'S':
                sx, sy = j, i

    print(simulate(H, W, N, maps, sx, sy))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# directions
x_dir = [0, 1, 0, -1]
y_dir = [1, 0, -1, 0]

# map info
visited = []
maps = []

# bfs algorithm
def bfs(h, w, cheese, sx, sy, moves):
    que = [(moves, sx, sy)]

    for i in range(h):
        for j in range(w):
            visited[i][j] = (maps[i][j] != 'X')

    visited[sy][sx] = False

    while len(que) > 0:
        c_moves, c_x, c_y = que.pop(0)
        if maps[c_y][c_x] == cheese:
            return (c_moves, c_x, c_y)

        for i in range(4):
            n_x = c_x + x_dir[i]
            n_y = c_y + y_dir[i]

            if(0 <= n_x < w and 0 <= n_y < h and visited[n_y][n_x]):
                que.append((c_moves+1, n_x, n_y))
                visited[n_y][n_x] = False

    return (-1, -1, -1)

# main function
if __name__ == '__main__':
    inputs = (input()).split()

    H = int(inputs[0])
    W = int(inputs[1])
    N = int(inputs[2])

    visited = [[True for i in range(W)] for j in range(H)]
    maps = ["" for i in range(H)]

    x, y = 0, 0
    for i in range(H):
        maps[i] = input()
        for j in range(W):
            if maps[i][j] == 'S':
                x, y = j, i

    moves = 0
    for i in range(1, N+1, 1):
        moves, x, y = bfs(H, W, str(i), x, y, moves)

    print(str(moves))
N, A, B, K = map(int, input().split())

mod = 998244353
F = [1]
RF = []


def inv(x):
    res = 1
    k = mod - 2
    y = x
    while k:
        if k & 1:
            res = (res * y) % mod
        y = (y * y) % mod
        k //= 2
    return res


def init():
    for i in range(N):
        F.append((F[i] * (i + 1)) % mod)
    for i in F:
        RF.append(inv(i))


def comb(x, y):
    return (F[x] * ((inv(F[x - y]) * inv(F[y])) % mod)) % mod


ans = 0
init()
for a in range(N):
    b = (K - a * A) / B
    if b < 0:
        break
    if b.is_integer():
        ans += (comb(N, a) * (comb(N, int(b)))) % mod
print(ans % mod)


### FIXED CODE ###

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

mod = 998244353
fact = [1] * (N + 1)
ifact = [1] * (N + 1)


def init():
    for i in range(N):
        fact[i + 1] = fact[i] * (i + 1) % mod
        ifact[i + 1] = pow(fact[i + 1], mod - 2, mod)


def comb(x, y):
    if y < 0 or y > x:
        return 0
    return (fact[x] * ifact[x - y] * ifact[y]) % mod


ans = 0
init()
for a in range(N + 1):
    n = K - a * A
    if n < 0:
        break
    if n % B == 0:
        ans += (comb(N, a) * (comb(N, n // B))) % mod
print(ans % mod)
s = input()
a = s[0]
b = s[1]
c = s[2]
d = s[3]

if a=b and c=d:
  print("Yes")
elif a=c and b=d:
  print("Yes")
elif a=d and b=c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = input()
a = s[0]
b = s[1]
c = s[2]
d = s[3]

if a==b==c==d:
  print("No")
elif a==b and c==d:
  print("Yes")
elif a==c and b==d:
  print("Yes")
elif a==d and b==c:
  print("Yes")
else:
  print("No")
sen = [A,B,C]
sen = sen.sort()
if sen = [5,5,7]:
	print("YES")
else:
	print("NO")

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

sen = [A, B, C]
x = max(sen)
y = min(sen)
if x == 7 and y == 5 and sum(sen) - x - y == 5:
    print("YES")
else:
    print("NO")
import sys
H,W,M=map(int, input().split())
h=[]
w=[]
Hcount=[0 for _ in range(H)]
Wcount=[0 for _ in range(W)]
B = [[0 for i in range(W)] for j in range(H)] ##掛け算で書いてはいけない

for i in range(M):
    hi,wi=map(int, input().split())
    h.append(hi)
    w.append(wi)
    Hcount[hi-1]+=1
    Wcount[wi-1]+=1
    B[hi-1][wi-1]=1
h_max=[i for i, v in enumerate(Hcount) if v == max(Hcount)]
w_max=[i for i, v in enumerate(Wcount) if v == max(Wcount)]
#print(h_max,w_max)
for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        if B[h_max[ii]][w_max[ii]]==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''for ii in range(len(h_max)):
    for jj in range(len(w_max)):
        h_cand=[k for k, v in enumerate(h) if v == h_max[ii]+1]
        w_cand=[l for l, v in enumerate(w) if v == w_max[jj]+1]
        h_set = set(h_cand)
        w_set = set(w_cand)
        matched_list = list(h_set & w_set)
        #print(h_cand,w_cand)
        #print(matched_list)
        if len(matched_list)==0:
            print(max(Hcount)+max(Wcount))
            sys.exit()
print(max(Hcount)+max(Wcount)-1)
'''

### FIXED CODE ###

import sys
 
input = sys.stdin.readline
 
 
def main():
    H, W, M = map(int, input().split())
    row = [0] * (H)
    col = [0] * (W)
    bomb = set()
    for _ in range(M):
        h, w = map(int, input().split())
        bomb.add((h, w))
        row[h-1] += 1
        col[w-1] += 1
    row_max = max(row)
    row_index_list = [i for i, v in enumerate(row) if v == row_max]
    col_max = max(col)
    col_index_list = [i for i, v in enumerate(col) if v == col_max]
    ans = row_max + col_max - 1
    c = False
    for x in row_index_list:
        for y in col_index_list:
            if not (x + 1, y + 1) in bomb:
                c = True
                break
        if c:
            break
    if c:
        ans += 1
    print(ans)
 
 
if __name__ == '__main__':
    main()
N = int(input())
P = list(map(int,input().split()))
List = []
ans = 0
for i in range(N):
  if(i == 0):
    ans += 1
  else:
    tmp = P.pop(0)
    List.append(tmp)
    if(P[i] <= min(List)):
      ans += 1
print(str(ans))

### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
mi = P[0]
ans = 0
for i in range(N):
  if(i == 0):
    ans += 1
  else:
    if(P[i] <= mi):
      ans += 1
      mi = P[i]
print(str(ans))
def execute(n, tn, m, pxm):
    result = []
    for px in pxm:
        cp = tn[:]
        cp[px[0] - 1] = px[1]
        result.append(sum(cp))
    return result


if __name__ == '__main__':
    n = int(input())
    tn = map(int, input().split())
    m = int(input())
    pxm = []
    for _ in range(m):
        p, x = map(int, input().split())
        pxm.append([p, x])
    print(execute(n, tn, m, pxm))


### FIXED CODE ###

def execute(n, tn, m, pxm):
    result = []
    for px in pxm:
        cp = tn[:]
        cp[px[0] - 1] = px[1]
        result.append(sum(cp))
    return result


if __name__ == '__main__':
    n = int(input())
    tn = list(map(int, input().split()))
    m = int(input())
    pxm = []
    for _ in range(m):
        p, x = map(int, input().split())
        pxm.append([p, x])
    result = execute(n, tn, m, pxm)
    print("\n".join(map(str, result)))
import numpy
a = list(map(int,input().split()))
b = list(map(int,input().split()))
for v in range(a[0]-a[1]+1):
  c=list(map(numpy.prod(b[0+v:a[0]+v]))
for m in range(a[0]-a[1]):
  if c[m+1]>c[m]:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

N,K=map(int,input().split())
a=list(map(int,input().split()))
for v in range(N-K):
  if a[v]>=a[K+v]:
    print("No")
  else:
    print("Yes")
kensa = 0
kekka = ""
num = []
hantei = "OK"
INF = input().split()
gyosu = int(INF[1])
keta = int(INF[0])
out = []
for l in range(keta):
  out.append(0)


for i in range(gyosu):
  num.append([int(j) for j in input().split()])

if gyosu >0:
  for j in range(gyosu-1):
    for k in range(gyosu-1):
      if num[j][0] == num[k + 1][0]:
        if num[j][1] != num[k + 1][1]:
          hantei = "NG"
          
    if num[j][0] == keta:
      if num[j][1] == 0:
        hantei ="NG"

if hantei == "NG":
  print("-1")
else:
  for m in range(gyosu):
    out[(num[m][0] - 1)] = num[m][1]
    #print(out)
  for n in range(keta):
    kekka = kekka + str(out[n])

  for p  in kekka:
      if p == "0":
        kensa = kensa + 1
      else:
        break
  for q in kensa:
    kekka.rstrip("0")

#    if n == 0 and keta != 1 and gyosu != 0:
      #print("-1")
      #hantei = "NG"

if hantei == "OK":
  if gyosu == 0:
    print(0)
  else:
    print(kekka)

### FIXED CODE ###

check = 0
check2 = 0
kensa = 0
kekka = "" 
num = []
hantei = "OK"
INF = input().split()
gyosu = int(INF[1])
keta = int(INF[0])
out = []
for l in range(keta):
  out.append(0)


for i in range(gyosu):
  num.append([int(j) for j in input().split()])

if gyosu > 0 :
  check = int(num[0][0])
  check2 = int(num[0][1])
  
  for j in range(gyosu-1):
    for k in range(gyosu-1):
      if num[j][0] == num[k + 1][0]:
        if num[j][1] != num[k + 1][1]:
          hantei = "NG"
    
    if int(num[j][0]) < check: # 入力値にある最大桁数を計算
      check = int(num[j][0])
      check2 = int(num[j][1])
  if check2 == 0:
    if check == 1 and keta == 3:
      hantei = "NG"
    if check == 2:
      hantei = "tokubetu2"
    if check == 3:
      hantei = "tokubetu"

if hantei == "NG":
  print("-1")
else:
  for m in range(gyosu):
    
    out[(num[m][0] - 1)] = num[m][1]
  for n in range(keta):
    kekka = kekka + str(out[n])

  for p  in kekka:
      if p == "0":
        kensa = kensa + 1
      else:
        break
  kekka2 = kekka
  for q in range(kensa):
    if keta != 1:
      kekka = kekka.lstrip("0")
if hantei == "OK":
  if gyosu == 0:
    if keta == 1:
      print("0")
    elif keta == 2:
      print("10")
    else:
      print("100")
  else:
    if keta == 2:
      if kensa == 1:
        kekka = "1" + kekka
    if keta == 3:
      if kensa == 1:
        kekka = "1" + kekka
      if kensa == 2:
        kekka = "10" + kekka
    print(kekka)

if hantei == "tokubetu":
  print("0")


if hantei == "tokubetu2":
  #kekka2 = kekka2.lstrip("0")
  kekka2 = kekka2[1:]
  kekka2 = "1" + kekka2
  print(kekka2)
a,b,c,d = [int(input()) for_ range(4)]
print(min(a,b)+min(c,d))

### FIXED CODE ###

a,b,c,d=[int(input()) for _ in range(4)]
print(min(a,b)+min(c,d))
print("ABD" int(input())>999 else "ABC")

### FIXED CODE ###

print("ABD" if int(input())>999 else "ABC")
import sys
sys.setrecursionlimit(10**7)
 
N,Q = (int(i) for i in input().split())
hen = {}
value = [0] * N

for _ in range(0,N-1):
    a,b = (int(i) for i in input().split())
    if a in hen:
        hen[a].append(b)
    else:
        hen[a] = [b]

for _ in range(0,Q):
    p,x = (int(i) for i in input().split())
    value[p-1] = value[p-1] + x

def add(p,x):
        for node in hen[p]:
            value[node-1] = value[node-1] + x
            if node in hen:
                add(node,value[node-1])

#add(1,value[0])
for i in range(0,n):
    if i+1 in hen:
        for node in hen[i+1]:
            value[node-1] += value[i]

print(' '.join(map(str,value)))
    


### FIXED CODE ###

a = int(input())
s=input()
if a < 3200:
    print('red')
else:
    print(s)
import math
N,Y=map(int,input().split())
YY=min(N,math.floor(Y/10000))
flag=False
for i in reversed(range(YY+1)):
    Y2=Y-i*10000
    N2=N-i
    YYY=min(N2,math.floor(YY2/5000))
    for j in reversed(range(YYY+1)):
        YY3=int((Y2-j*5000)/1000)
        if YY3==N2-j:
            print(str(i),"",str(j),"",str(YY3))
            flag=True
            break
        else:
            continue
if flag==False:
    print(str(-1),"",str(-1),"",str(-1) )
else:
    exit


### FIXED CODE ###

N,Y=map(int,input().split())
flag=False
for i in range(N+1):
    if flag==True:
        break
    else:
        pass
    for j in range(N+1-i):
        k=N-i-j
        if 10000*i+5000*j+1000*k==Y:
            print(i, j, k)
            flag=True
            break
        else:
            continue
if flag==False:
    print("-1 -1 -1")
else:
    pass
def main():
  S=input()
  N=len(S)
  s=0
  if N%2==0:
    for i in range(N//2):
      if S[i]!=S[N-1-i]:
        S[N-1-i]=S[i]
        s+=1
  else:
     for i in range(N//2):
       if S[i]!=S[N-1-i]:
         S[N-1-i]=S[i]
         s+=1
  print(s)
main()
  
      

### FIXED CODE ###

def main():
  S=input()
  s=0
  N=len(S)
  for i in range(N//2):
    if S[i]!=S[N-1-i]:
      s+=1
  print(s)
main()
import numpy as np
INF = pow(10, 9)


def main():
    n, m, x = map(int, input().split())
    i = 0
    c = []
    a = []

    for i in range(n):
        tmp = list(map(int, input().split()))
        c.append(tmp[0])
        a.append(tmp[1:])

    ans = INF
    for i in range(2**n):
        tmp = np.array([0 for i in range(m)])
        cost = 0
        flag = True
        for j in range(n):
            if ((i >> j) & 1) == 1:
                tmp += a[j]
                cost += c[j]
        # print(tmp)
        for j in range(m):
            if tmp[j] < x:
                flag = False
                break
        # print(cost)
        if flag == True:
            if cost < ans:
                ans = cost
    print(ans) if ans != INF else print(-1)

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = pow(10, 9)


def main():
    n, m, x = map(int, input().split())
    i = 0
    c = []
    a = []

    for i in range(n):
        tmp = list(map(int, input().split()))
        c.append(tmp[0])
        a.append(tmp[1:])

    ans = INF
    for i in range(2**n):
        tmp = [0 for i in range(m)]
        cost = 0
        flag = True
        for j in range(n):
            if ((i >> j) & 1) == 1:
                tmp = [x+y for x, y in zip(tmp, a[j])]
                cost += c[j]
        # print(tmp)
        for j in range(m):
            if tmp[j] < x:
                flag = False
                break
        # print(cost)
        if flag == True:
            if cost < ans:
                ans = cost
    print(ans) if ans != INF else print(-1)

    return


if __name__ == "__main__":
    main()
def partpall(s,n):
	if s!=s[::-1]:
		return False
	else:
		return True

def pall(s,n):
	if s!=s[::-1]:
		return False
	return partpall(s[n//2 +1 :],n) and partpall(s[:n//2 ],n)


# s=input("enter:")
s="akakaka"
# print("sucess",s,s[::-1])
# revStr=s[::-1]
#n=len(s)
# print(n)
if pall(s,n):
	print("Yes")
else:
	print("No")

### FIXED CODE ###

def partpall(s,n):
	if s!=s[::-1]:
		return False
	else:
		return True

def pall(s,n):
	if s!=s[::-1]:
		return False
	return partpall(s[n//2 +1 :],n) and partpall(s[:n//2 ],n)


# s=input("enter:")
s=input()
# print("sucess",s,s[::-1])
# revStr=s[::-1]
n=len(s)
# print(n)
if pall(s,n):
	print("Yes")
else:
	print("No")
import math

a, b, c = input().split()
a = math.sqrt(int(a))
b = math.sqrt(int(b))
c = math.sqrt(int(c))
d = a + b - c

if d < 0:
    if math.isclose(d, 0.0):
        print('No')
    else:
        print('Yes')
else:
    print('No')


### FIXED CODE ###

from decimal import Decimal

a, b, c = input().split()
a = Decimal(int(a)).sqrt()
b = Decimal(int(b)).sqrt()
c = Decimal(int(c)).sqrt()

d = a + b

if d < c:
    print('Yes')
else:
    print('No')
n = int(input())
s = input()
a = 0
for i in range(1,n):
    a = max(a,set(s[:i]) & set(s[i:]))

print(a)


### FIXED CODE ###

n = int(input())
s = input()
a = 0
for i in range(1,n):
    a = max(a, len(set(s[:i]) & set(s[i:])))

print(a)
if (B-A+1) < K:
    for i in range(A, B+1):
        print(i)
    exit()

lst = list(range(A, B+1))
lst.sort()

x = [lst[i] for i in range(0, K)]
y = [lst[i] for i in range(-1, -K-1, -1)]

ans = list(set(x) | set(y))
ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(b, a + k - 1) + 1):
    print(i)
for i in range(max(b - k + 1, a + k), b + 1):
    print(i)
r = float(input().split())
print("%.5f %.5f" %(r**2*3.14, 2*r*3.14))


### FIXED CODE ###

#
# 4b
#
import math


def main():
    r = float(input())
    S = r * r * math.pi
    L = 2 * r * math.pi
    print(f"{S:.6f} {L:.6f}")


if __name__ == '__main__':
    main()
n,k = map(int,input().split())
a = list(map(int,input().split()))
z = 0
b = [1]
c = [0]*n
for i in range(n*3):
  j = [a[b[i]-1]]
  b.extend(j)
  c[a[b[i]-1]-1] = c[a[b[i]-1]-1]+1
  if c[a[b[i]-1]-1] == 2:
    z = z + 1
if k <= n:
  y = b[k]
else:
  l = (k-n)%z
  y = b[n+l]
print(y)

### FIXED CODE ###

s = input()
t = input()

n = len(s)
if s+t[n] == t:
  print("Yes")
else:
  print("No")
import collections
n, q = map(int, input().split())

tree = collections.defaultdict(list)
counter = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    counter[a] = 0
    counter[b] = 0

for _ in range(q):
    p, x = map(int, input().split())

    def add(p_, x_):
        counter[p_] += x_
        for v in tree[p_]:
            add(v, x_)

    add(p, x)

print(' '.join(str(v) for _, v in sorted(counter.items(), key=lambda x: x[0])))


### FIXED CODE ###

a = int(input())
s = input()

if a < 3200:
    print('red')
else:
    print(s)
from heapq import heappush, heappop

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)
cand = []

for i in range(len(A)):
    for j in range(len(B)):
        if(i + j + 1 >= K):
            break
        for k in range(len(C)):
            if(i + j + k + 1 >= K):
                break
            heappush(cand, -(A[i]+B[j]+C[k]))

for i in range(K):
    print(-heappop(cand))
    


### FIXED CODE ###

from heapq import heappush, heappop

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)
cand = []

for i in range(len(A)):
    for j in range(len(B)):
        if(i * j > K):
            break
        for k in range(len(C)):
            if(i *  j * k > K):
                break
            heappush(cand, A[i]+B[j]+C[k])
            if(len(cand) > K):
                heappop(cand)

ret = []
for i in range(K):
    ret.append(heappop(cand))

for i in reversed(range(K)):
    print(ret[i])
s=input()
t=input()

ls=len(s)
lt=len(t)

dp=[[0]*(lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=""
l=dp[ls][lt]-1
i=ls-1
j=lt-1
while l>=0:
    if s[i]==t[j]:
        ans=s[i]+ans
        i-=1
        j-=1
        l-=1
    else:
      	if dp[i-1][j]>dp[i][j-1]:
        i-=1
    else:
        j-=1

print(ans)

### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1

        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    # print(dp[i])
ans=''
i,j=len(s),len(t)
while i > 0 and j > 0:
  if s[i-1]==t[j-1]:
    ans=s[i-1]+ans
    i=i-1
    j=j-1
  else:
    if dp[i-1][j]>dp[i][j-1]:
      i-=1
    else:
      j-=1
print(ans)
ai = lambda: list(map(int,input().split()))
ai_ = lambda: [int(x)-1 for x in input().split()]


n = int(input())
a = ai()
MOD = 10**9+7

from collections import Counter
dup = list(Counter(sorted(a)).values()).index(2)+1
ant = a.index(dup)
post = a[::-1].index(dup)


def nCb(n, r):
    fac = [1, 1] + [0] * n
    finv = [1, 1] + [0] * n
    inv = [0, 1] + [0] * n
    for i in range(2, n + 2):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = -inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
        
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD


for k in range(1,n+2):
    if k == 1:
        print(n)
    else:
        ans = nCb(n+1,k)
        if ant+post+1 >= k:
            ans -= nCb(ant+post,k-1)
        print(ans)


### FIXED CODE ###

f = lambda: list(map(int,input().split()))
n = int(input())
a = f()
if n&1:
    b = a[::-2]+a[1::2]
else:
    b = a[::-2]+a[::2]
print(*b)
def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)

a,b,k=map(int,input().split())
z=gcd(a,b)
ans=[]
for i in range(1,z):
  if z%i==0:
    ans.append(i)
    
print(ans[-k])  
    

### FIXED CODE ###

def gcd(x,y):
  if x%y==0:
    return y
  else:
    return gcd(y,x%y)

a,b,k=map(int,input().split())
z=gcd(a,b)
ans=[]
for i in range(1,z+1):
  if z%i==0:
    ans.append(i)
    
print(ans[-k])
import math
from functools import reduce

N = int(input())
T = [int(input()) for _ in range(N)]

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(L):
    return reduce(lcm_base, L, 1)

print(lcm(T))

### FIXED CODE ###

import fractions
from functools import reduce

N = int(input())
T = [int(input()) for _ in range(N)]

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

def lcm(L):
    return reduce(lcm_base, L, 1)

print(lcm(T))
n = int(input())
a = []
d = {}
ans = 0
for _ in range(n):
    a.append(int(input()))
for i in a:
    d[i] = d.get(i,0) + 1
for key in d:
    ans += d[key]*(d[key]-1)//2
for i in a:
    print(ans + 1 - d[i])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
for i in a:
    d[i] = d.get(i,0) + 1
for key in d:
    ans += d[key]*(d[key]-1)//2
for i in a:
    print(ans + 1 - d[i])
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
	for j in range(W+1):
		if j-w[i] >= 0:
			dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]]+v[i])
		else:
			dp[i+1][j] = dp[i][j]
print(dp[N][W])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, W = MAP()
w, v = ZIP(N)
max_v = sum(v)
dp = [INF]*(max_v+1)
dp[0] = 0
for w, v in zip(w, v):
	for i in range(max_v, -1, -1):
		if i-v >= 0:
			dp[i] = min(dp[i], dp[i-v]+w)

ans = 0
for i in range(len(dp)):
	if dp[i] <= W:
		ans = i
print(ans)