Harryxun/stf_run huggingface dataset:
# 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
    global N
    global M

    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)
#-*- coding: utf-8 -*-

price = 700
S = raw_input()
for i in S:
    if i= 'o':
        price = price + 100
print price

### FIXED CODE ###

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

price = 700
S = input()
for i in S:
    if i == 'o':
        price = price + 100
print(price)
bingo = []
for i in range(3):
    array = list(map(int, input().strip().split()))
    bingo.append(array)

N = int(input())
number = []

for j in range(N):
    number.append(int(input()))

result = []
for n in range(N):
    for t in range(3):
        for y in range(3):
            if(bingo[t][y] == number[n]):
                result.append([t,y])

bingo_a = 'No'
t_a = 0
for r in range(len(result)):
    for t in range(3):
        for y in range(3):
            if(result[r][0] == t and result[r][1] == y):
                t_a += 1
        if(t_a == 3):
            bingo_a = 'Yes'

y_a = 0
for r in range(len(result)):
    for y in range(3):
        for t in range(3):
            if(result[r][0] == t and result[r][1] == y):
                y_a += 1
        if(y_a == 3):   
            bingo_a = 'Yes'

ans = 0
for rr in range(len(result)):
    if(result[rr][0] == 0 or result[rr][1] == 0):
        ans = ans + 1
    if(result[rr][1] == 1 or result[rr][1] == 1):
        ans = ans + 1
    if(result[rr][0] == 2 or result[rr][1] == 2):
        ans = ans + 1
if(ans == 3):
    bingo_a = 'Yes'

ans = 0
for rr in range(len(result)):
    if(result[rr][0] == 0 or result[rr][1] == 2):
        ans = ans + 1
    if(result[rr][1] == 1 or result[rr][1] == 1):
        ans = ans + 1
    if(result[rr][0] == 2 or result[rr][1] == 0):
        ans = ans + 1
if(ans == 3):
    bingo_a = 'Yes'

print(bingo_a)

### FIXED CODE ###

N = int(input())
print(int(N / 2 + 0.5))
X = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

x = int(input())
if x >= 30:
  print("Yes")
else:
  print("No")
a,b,k = input().split()

for i in range(k):
  if a > 0:
    a -= 1
  elif b > 0:
    b -= 1

print(a + " " + b)

### FIXED CODE ###

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

A -= K
if(A < 0):
    B -= abs(A)
    A = 0
    if(B < 0):
        B = 0

print(str(A) + " " + str(B))
D,T,S = map(int , input().split().split())

if D > S * T:
  print("no")
  
else:
  print("yes")

### FIXED CODE ###

a,b,c = (int(x) for x in input().split())

if a > b * c:
  print("No")
  
else:
  print("Yes")
A,B,C,K = map(int,input().split())
 
if K <= A:
  print(K)
elif K <= (A+B):
  print(A)
else:
  print(A-(K-(A+B)))

### FIXED CODE ###

S = input()
T = input()

T2 = T[:len(T)-1]

if S == T2:
  print("Yes")
else:
  print("No")
input_ = [input() for i in range(4)]

N, K, X, Y = input_

acc = 0

if N > K:
    acc = int(K) * int(X) + (int(N) - int(K)) * int(Y)
else:
    acc = int(N) * int(X)

print(acc)

### FIXED CODE ###

N = int(input())
sigma = 0

for i in range(N + 1):
    sigma += i

print(sigma)
a,b = input().split()

if a=='H':
    if b=='H':
        print('H')
    else:
        print('D')
else:
    if b==H:
        print('D')
    else:
        print('H')

### FIXED CODE ###

a,b = input().split()

if a=='H':
    if b=='H':
        print('H')
    else:
        print('D')
else:
    if b=='H':
        print('D')
    else:
        print('H')
n = int(input())
ans = [-1]*n
data =[[] for i in range(n+1)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    data[u].append([v,w])
    data[v].append([u,w])

ans[0] = 1
def color(i):
    for v,w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(0)
for i in range(n):
    print(ans[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
ans = [-1]*(n+1)
data =[[] for i in range(n+1)]

for i in range(n-1):
    u,v,w = map(int,input().split())
    data[u].append([v,w])
    data[v].append([u,w])

ans[1] = 1
def color(i):
    for v, w in data[i]:
        if ans[v] == -1:
            if w % 2 == 0:
                ans[v] = ans[i]
            else:
                ans[v] = 1 - ans[i]
            color(v)
    return

color(1)
for i in range(n):
    print(ans[i+1])
import numpy as np
n = int(input())
ab = [list(map(int, input().split())) for x in range(n)]

cnt = 0
for a, b in reversed(ab):
    diff = a - b + cnt
    if diff == -b:
        pass
    elif diff < 0:
        cnt -= diff
    else:
        diffb = diff % b
        if diffb:
            cnt += b - diffb
print(int(cnt))



### FIXED CODE ###

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

for x in range(n + 1):
    for y in range(m + 1):
        if m * x + n * y - x * y * 2 == k:
            print("Yes")
            sys.exit()
print("No")
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
N,K=map(int,input().split())

#A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
A=list(map(int,input().split()))
A.sort()
mod=10**9+7
fac=[1,1]
for i in range(2,N+1):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

if K==1:
    print(0)


count=0
ncount=0
for i in range(N-K+1):
    n=N-i-K
    m=i+1

    ncount+=fac[m]*ifac[K-2]*ifac[m-(K-2)]%mod
    ncount%=mod
    count-=A[n]*ncount
    count%=mod

ncount=0
for i in range(K-1,N):
    n=i-1
    #print(n,K-2,n-(K-2))
    ncount+=fac[n]*ifac[K-2]*ifac[n-(K-2)]%mod
    ncount%=mod
    count+=A[i]*ncount
    count%=mod
print(count)


### FIXED CODE ###

mod = 10**9 + 7
kaijotable = [0 for i in range(200100)]
kaijotable[0] = 1
for i in range(1, 200051):
    kaijotable[i] = (kaijotable[i - 1] * i) % mod

def doubling(x, y, mod):
    if y == 0:
        return 1
    if y == 1:
        return x
    elif y % 2 == 0:
        val = (doubling(x, y // 2, mod) ** 2) % mod
        return val
    else:
        val = (doubling(x, y // 2, mod) ** 2) * x % mod
        return val

def gyaku(x):
    gyaku = doubling(x, mod - 2, mod) % mod
    return gyaku

gyakutable = [0 for i in range(200100)]
gyakutable[200050] = gyaku(kaijotable[200050])
for i in range(200050, 0, -1):
    gyakutable[i - 1] = i * gyakutable[i] % mod

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
value=0
mod=10**9 + 7
if K==1:
    print(0)
    exit()

z=0

for i in range(N):
    if i>=K-1:
        c=kaijotable[z+K-1] * gyakutable[K-1] * gyakutable[z+K-1-(K-1)] % mod
        value+=c*A[i]
        value-=c*A[N-1-i]

        z+=1
    value%=mod
print(value)
a=input()
if a%2==0:
    print(a)
else
    print(a*2)

### FIXED CODE ###

N=input()
N=int(N)
if N%2==0:
    print(N)
else:
    print(N*2)
8
-406 10
512 859
494 362
-955 -475
128 553
-986 -885
763 77
449 310

### FIXED CODE ###

import numpy as np
import itertools 
def distance(a,b):
    x1,y1 = a
    x2,y2 = b
    return np.sqrt((x1-x2)**2 + (y1- y2)**2)
n = int(input())
xy = []
for _ in range(n):
    x,y = map(int,input().split())
    xy.append([x,y])
n_permutations = itertools.permutations(range(n))
dist_list=[]
for one_case in n_permutations:
    dist = 0
    for i in range(n-1):
        a = xy[one_case[i]]
        b = xy[one_case[i+1]]
        dist += distance(a,b)
    dist_list.append(dist)
print(sum(dist_list)/len(dist_list))
s = input()
K = int(input())
arr = set()
for i in range(len(s)):
    for j in range(i+1,min(i+1+K,len(s))):
        arr.add(s[i:j])
print(list(sorted(arr))[K-1])

### FIXED CODE ###

s = input()
K = int(input())
arr = set()
for i in range(len(s)):
    for j in range(i+1,min(i+1+K,len(s)+1)):
        arr.add(s[i:j])
print(sorted(arr)[K-1])
n, k = map(int, input().split())
p = list(map(int, input().split()))
ans_max = 0
for i in range(n-2):
    ans_max = max(ans_max, sum(p[i:i+k]))
    if sum(p[i: i+k]) == ans_max:
        ans = i
print((sum(p[ans: ans+k]) + k) / 2)


### FIXED CODE ###

from itertools import accumulate
n, k = map(int, input().split())
p = list(map(int, input().split()))
p_acc = list(accumulate(p))
ans_max = p_acc[k-1]
ans = 0
if n > k:
    for i in range(n-k):
        ans_max = max(ans_max, p_acc[i+k] - p_acc[i])
        if p_acc[i+k] - p_acc[i] == ans_max:
            ans = i
    print((p_acc[ans+k] - p_acc[ans] + k) / 2)
else:
    print((sum(p) + n) / 2)
import math
A,B,C=map(int,input().split())
lcm = A*B//math.gcd(A,B)
#A*(i+j)%B=C
#A*(i+j)=BX+C
i=A
while i<=lcm:
  if i%B==C:
    print("YES")
    exit()
  i*=A
print("NO")

### FIXED CODE ###

import fractions
A,B,C=map(int,input().split())
lcm = A*B#//fractions.gcd(A,B)
#A*(i+j)%B=C
#A*(i+j)=BX+C
i=A
while i<=lcm:
  #print(i,lcm)
  if i%B==C:
    print("YES")
    exit()
  i+=A
print("NO")
a=int(input())
b=int(input())

if a*b%2==0:
    print('Even')
else:
    print('Odd')

### FIXED CODE ###

a,b=map(int,input().split())
 
if a*b%2==0:
    print('Even')
else:
    print('Odd')
a = float(input())
b =float(input())
print(a+b,a*b)




### FIXED CODE ###

a,b = map(int,input().split())
print(a*b,2*(a+b))
A, B, C, K = map(int, input().split())
print(A-B) if k%2==0 else print(B-A)

### FIXED CODE ###

A, B, C, K = map(int, input().split())
print(A-B) if K%2==0 else print(B-A)
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()
    Bs = [(b, c) for b, c in zip(B, C)]
    Bs.sort(key=lambda x: x[1], reverse=True)
    i = 0
    flag = False
    for b, c in Bs:
        for j in range(b):
            if A[i] >= c:
                flag = True
                break
            A[i] = c
            i += 1
        if flag:
            break
    print(sum(A))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    A.sort()
    Bs = [(b, c) for b, c in zip(B, C)]
    Bs.sort(key=lambda x: x[1], reverse=True)
    i = 0
    flag = False
    for b, c in Bs:
        for j in range(b):
            if i >= N:
                flag = True
                break
            if A[i] >= c:
                flag = True
                break
            A[i] = c
            i += 1
        if flag:
            break
    print(sum(A))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[0:mini])
    if mini != d-1:
        result += minisum(x[mini+1:d])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))


### FIXED CODE ###

X = input()
ctr = 0
ans = 0
for i in X:
    if i == 'T':
        if ctr > 0:
            ctr -= 1
        else: 
            ans += 1
    else:
        ctr += 1
print(2*ans)
print(-int(input())+sum(int(i) for i in input().split())))

### FIXED CODE ###

print(-int(input())+sum(int(i) for i in input().split()))
n=int(input)

if n==1:
  print("Hello World")
else:
  A=int(input())
  B=int(input())
  print(A+B)

### FIXED CODE ###

n=int(input())

if n==1:
  print("Hello World")
else:
  A=int(input())
  B=int(input())
  print(A+B)
S=input()
Q=[s for s in S if s != 'A']
U=list('KIHBR')
import sys
if S.count('A')>4:
    print('NO')
    sys.exit()
for i in range(len(S)-1):
    if S[i]==S[i+1]:
        print('NO')
        sys.exit()
    elif S[i]=='K' and S[i+1]!='I':
        print('NO')
        sys.exit()
for i in range(len(S)):
    if Q[i]==U[i]:
        pass
    else:
        print('NO')
        break
else:
    print('YES')

### FIXED CODE ###

S=input()
Q=[s for s in S if s != 'A']
U=list('KIHBR')
import sys
if S.count('A')>4:
    print('NO')
    sys.exit()
elif len(Q)!=5:
    print('NO')
    sys.exit()
for i in range(len(S)):
    if S[i] not in list('AKIHABARA'):
        print('NO')
        sys.exit()
for i in range(len(S)-1):
    if S[i]==S[i+1]:
        print('NO')
        sys.exit()
    elif S[i]=='K' and S[i+1]!='I':
        print('NO')
        sys.exit()
    elif S[i]=='I' and S[i+1]!='H':
        print('NO')
        sys.exit()
for i in range(len(U)):
    if Q[i]==U[i]:
        pass
    else:
        print('NO')
        break
else:
    print('YES')
def F(n):
    if n <1:
        return 1
    elif n < 3:
        return 0
    elif n < 6:
        return 1
    else:
        return F(n - 1) + F(n - 3)


s = int(input())
print(F(s) % (10 ** 9 + 7))

### FIXED CODE ###

S = int(input())
DP = [0] * (S + 1)
Mod = 10 ** 9 + 7

if S >= 3:
    DP[0] = 1
    DP[1] = 0
    DP[2] = 0
    for TS in range(3,S+1):
        DP[TS] = DP[TS-1] + DP[TS-3]
    print(DP[S] % Mod)
else:
    print(0)
S=int(input())
l=[]
while S>0:
  l.append(S%10)
  S//=10
if l[0]==l[1] or l[1]==l[2] or l[2]==l[3]:
  print('Bad')
else:
  print('Good')

### FIXED CODE ###

S=input()
s=str(S)
if s[0]==s[1] or s[1]==s[2] or s[2]==s[3]:
  print('Bad')
else:
  print('Good')
if S=="SUN":
  print(7)
elif S=="MON":
  print(6)
elif S=="TUE":
  print(5)
elif S=="WED":
  print(4)
elif S=="THU":
  print(3)
elif S=="FRI":
  print(2)
elif S=="SAT":
  print(1)

### FIXED CODE ###

S=input()
if S=="SUN":
  print(7)
elif S=="MON":
  print(6)
elif S=="TUE":
  print(5)
elif S=="WED":
  print(4)
elif S=="THU":
  print(3)
elif S=="FRI":
  print(2)
elif S=="SAT":
  print(1)
N=int(input())
print(N*2 if N%==1 else N)

### FIXED CODE ###

N=int(input())
print(N*2 if N%2==1 else N)
n=int(input())
a=[0]
a.append(map(int,input().split()))
a.append(0)
s=abs(a[0])+abs(a[n-1])
for i in range(n-1):
  s+=abs(a[i]-a[i+1])
for i in range(1,n):
  if min(a[i+1],a[i-1])<=a[i]<=max(a[i-1],a[i+1]):
    print(s)
  elif a[i]<=min(a[i-1],a[i+1])<=max(a[i-1],a[i+1]):
    print(s-2*abs(a[i]-min(a[i+1],a[i-1])))
  else:
    print(s-2*abs(max(a[i-1],a[i+1])-a[i]))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
a=[0]
for i in range(n):
  a.append(h[i])
a.append(0)
s=0
for i in range(n+1):
  s+=abs(a[i]-a[i+1])
for i in range(1,n+1):
  if min(a[i+1],a[i-1])<=a[i]<=max(a[i-1],a[i+1]):
    print(s)
  elif a[i]<=min(a[i-1],a[i+1])<=max(a[i-1],a[i+1]):
    print(s-2*abs(a[i]-min(a[i+1],a[i-1])))
  else:
    print(s-2*abs(max(a[i-1],a[i+1])-a[i]))
N=int(input())
S=str(input())

ans=N

for i in range(N-1):
    if S[i]=S[i+1]:
        ans-=1

print(ans)






### FIXED CODE ###

N=int(input())
S=str(input())

ans=N

for i in range(N-1):
    if S[i]==S[i+1]:
        ans-=1

print(ans)
N = int(input())
S,T =  input().split()
ans = ""
for i,j in zip(S,T):
  ans = ans+i+j
  
print(ans)

### FIXED CODE ###

a = int(input())
b = int(input())

arr = [1,2,3]
arr.remove(a)
arr.remove(b)
print(arr[0])
a, b, x = map(int,input().split())
    if x >= a**2*b/2:
        ans = np.arctan(2*(b-x/a**2)/a)
    else:
        ans = np.arctan(a*b/2/x*b)
    print(ans*180/np.pi)

### FIXED CODE ###

import numpy as np
a, b, x = map(int,input().split())
if x >= a**2*b/2:
    ans = np.arctan(2*(b-x/a**2)/a)
else:
    ans = np.arctan(a*b/2/x*b)
print(ans*180/np.pi)
N=int(input())
A=list(input().split())
num=int(A[0])
while num%2!=1 and num>0:
    num=num/2
    cnt+=1
mini=cnt
for i in range(N):
    cnt=0
    num=int(A[i])
    while num%2!=1 and num>0:
        num=num/2
        cnt+=1
    if cnt<mini:
        mini=cnt
print(mini)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
 
while True:
    for i in range(len(A)):
        if A[i]%2 != 0:
            break
        elif A[i]%2 == 0:
            A[i] /= 2
    else:
        cnt += 1
        continue
    break
    
print(cnt)
import math
n,d = map(int,input().split())
count = 0
for i in range(n):
  x = list(map(int, input().split()))
for i in range(d):
  n=0
  for j in range(d) if i < j:
    n += (x[i][j]-x[i+1][j])**2
  m = math.sqrt(n)
  if m.is_integer():
    count +=1

print(count)


### FIXED CODE ###

import math
N,D = map(int,input().split())
X = [list(map(int, input().split())) for i in range(N)]
count = 0
for i in range(N):
    for j in range(i+1,N):
        n = 0
        for k in range(D):
            n = n + (X[i][k]-X[j][k])**2
        n = math.sqrt(n)
        if n.is_integer():
            count += 1
print(count)
N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

kbit = []
k = K
for i in range(100000000):
  if (k == 0):
    break
  kbit.append( k%2 )
  k//=2
keta = len(kbit)

def chk(c):
  #print (c)
  s = 0
  for k,v in li:
    if ( (c^k)|c == c ):
      #print ( k,v,"ok" )
      s += v
  return s

ma = 0
ma = max(ma, chk( (1<<(keta-1))-1) )
ma = max(ma, chk ( K ) )

for i in range(keta):
  if ( kbit[keta-1-i] == 0 ):
    continue
  else:
    bit = [0]*(keta)
    for j in range(keta):
      if (i<j):
        bit[keta-1-j]=1
      elif (j<i):
        bit[keta-1-j]=kbit[keta-1-j]
      else:
        bit[keta-1-j]=0
    
    v = 0
    for j in range(keta):
      if (bit[j]==1):
        v += 2**(j)
    #print ( v , bit )
    ma = max(ma, chk ( v ) )
print ( ma )


### FIXED CODE ###

N,K = [ int(it) for it in input().split() ]
li = [ [ int(it) for it in input().split() ] for i in range(N) ]

kbit = []
k = K
for i in range(100000000):
  if (k == 0):
    break
  kbit.append( k%2 )
  k//=2
keta = len(kbit)

def chk(c):
  #print (c)
  s = 0
  for k,v in li:
    if ( (c^k)|c == c ):
      #print ( k,v,"ok" )
      s += v
  return s

ma = 0

if (K<100):
  for i in range(K+1):
  	ma = max(ma, chk(i))
else:
  ma = max(ma, chk( 0 ))
  ma = max(ma, chk( 1 ))
  ma = max(ma, chk( 2 ))
  ma = max(ma, chk( 3 ))
  ma = max(ma, chk( 4 ))
  ma = max(ma, chk( (1<<(keta-1))-1) )
  ma = max(ma, chk ( K ) )

  for i in range(keta):
    if ( kbit[keta-1-i] == 0 ):
      continue
    else:
      bit = [0]*(keta)
      for j in range(keta):
        if (i<j):
          bit[keta-1-j]=1
        elif (j<i):
          bit[keta-1-j]=kbit[keta-1-j]
        else:
          bit[keta-1-j]=0

      v = 0
      for j in range(keta):
        if (bit[j]==1):
          v += 2**(j)
      #print ( v , bit )
      ma = max(ma, chk ( v ) )
print ( ma )
import sys
input = sys.stdin.readline
s = list(input().rsteip())
S = s[1::2]
print("".join(S))

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = list(input().rstrip())
S = s[::2]
print("".join(S))
for i in range(1,4):
    if s[0] == s[i]:
        for j in range(2,4):
            if s[1] == s[j]
    else:
        print("No") 
        exit()
print("Yes")

### FIXED CODE ###

s = input()
s_list = list(s)
s_list.sort()

if s_list[0] == s_list[1] and s_list[2] == s_list[3] and s_list[0] != s_list[2]:
    print("Yes")
else:
    print("No")
class Solver:

    def __init__(self):
        pass

    def solve(self, a, b, k):
        for n in range(min(a,b), 0, -1):
            if (a % n) == 0 and (b % n) ==0:
                k -= 1
                if k == 0:
                    return n
        return 1


if __name__ == '__main__':

    solver = Solver()

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

    n = solver.solve(a, b, k)
    print(n)
(atcoder) @lx

### FIXED CODE ###

class Solver:

    def __init__(self):
        pass

    def solve(self, a, b, k):
        for n in range(min(a,b), 0, -1):
            if (a % n) == 0 and (b % n) ==0:
                k -= 1
                if k == 0:
                    return n
        return 1


if __name__ == '__main__':

    solver = Solver()

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

    n = solver.solve(a, b, k)
    print(n)
while True:
    try:
        n = int(raw_input())
        filter = [1 for i in range(n)]
        filter[0] = 0
        for i in range(2,n//2):
　　　　　　　if filter[i] = 1
                j = 2
                k = i*j
                while k < n:
                    filter[k-1] = 0
                    j += 1
                    k = i*j
        print filter
        sum = 0
        for i in filter:
            sum += i
        print sum
    except:
        break

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])
a, b, k = map(int, input().split())


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


a = set(make_divisors(a))
b = set(make_divisors(b))

ans = list(a & b)

print(ans[1])

### FIXED CODE ###

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

cnt = 0
for i in range(min(a, b), 0, -1):
    if a % i == 0 and b % i == 0:
        cnt += 1
    if cnt == k:
        break

print(i)