Harryxun/stf_run huggingface dataset:
N,M,K=map(int,input().split())
P=998244353

start=(M*pow(M-1,N-1,P))%P

fac=[0]*N
finv=[0]*N
inv=[0]*N
fac[0]=1
fac[1]=1
finv[0]=1
finv[1]=1
inv[1]=1
for i in range(2,N):
    fac[i]=(fac[i-1]*i)%P
    inv[i]=P-(inv[P%i]*(P//i))%P
    finv[i]=(finv[i-1]*inv[i])%P

def comb(n,k):
    return fac[n]*(finv[k]*finv[n-k]%P)%P



comp=0
last=(N-1)-K #K=0ならthru
if K>=1:
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
comp=(comp*M)%P

print((start+comp)%P)

### FIXED CODE ###

N,M,K=map(int,input().split())
P=998244353

start=(M*pow(M-1,N-1,P))%P



if N>=2:
    fac=[0]*N
    finv=[0]*N
    inv=[0]*N
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1
    for i in range(2,N):
        fac[i]=(fac[i-1]*i)%P
        inv[i]=P-(inv[P%i]*(P//i))%P
        finv[i]=(finv[i-1]*inv[i])%P

    def comb(n,k):
        return fac[n]*(finv[k]*finv[n-k]%P)%P



    comp=0
    last=(N-1)-K #K=0ならthru
    for i in range(1,K+1):
        comp=(comp+comb(N-1,i)*pow(M-1,(N-1)-i,P))%P
    comp=(comp*M)%P

    print((start+comp)%P)

else:
    print(M%P)
def solve(string):
    n, k, *a = map(int, string.split())
    if k == 0:
        x = 0
    else:
        l = len("{:b}".format(k))
        count = [0] * l
        for _a in a:
            if _a == 0:
                continue
            tmp = "{:b}".format(_a)
            for i, _f in enumerate(tmp[::-1]):
                if _f == "1":
                    count[l - i - 1] += 1
        x = int("".join(["1" if _c < n / 2 else "0" for _c in count]), 2)
    return str(sum([x ^ _a for _a in a]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

def solve(string):
    n, k, *a = map(int, string.split())
    if k == 0:
        x = 0
    else:
        l = len("{:b}".format(k))
        base = [2**(l - i - 1) for i in range(l)]
        count = [0] * l
        for _a in a:
            tmp = "{:b}".format(_a)
            for i, _f in enumerate(tmp[::-1]):
                if i >= l:
                    break
                if _f == "1":
                    count[l - i - 1] += 1
        x = 0
        for _c, _b in zip(count, base):
            if _c < n / 2 and x + _b <= k:
                x += _b
    return str(sum([x ^ _a for _a in a]))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
N, A, B = list(map(int, input().rstrip().split(' ')))
LIST_RESULT = []

for i in range(1, N+1):
    str_i = str(i)
    l = len(str_i)

    sum = 0
    for x in range(l):
        sum += int(str_i[x])
    if A <= sum and sum <= B:
        LIST_RESULT.append(sum)

sum_result = sum(LIST_RESULT)
print(sum_result)

### FIXED CODE ###


N, A, B = list(map(int, input().rstrip().split(' ')))
LIST_RESULT = []

for i in range(1, N+1):
    str_i = str(i)
    l = len(str_i)

    sum_tmp = 0
    for x in range(l):
        sum_tmp += int(str_i[x])
    if A <= sum_tmp and sum_tmp <= B:
        LIST_RESULT.append(i)

sum_result = sum(LIST_RESULT)
print(sum_result)
n, m = map(int, input().split())
c = [input().split() for i in range(m)]
for i in range(m):
    c[i][0] = int(c[i][0])
AC, WA = 0, 0
aclist = [0 for i in range(n)]
for i in range(m):
    if aclist[c[i][0]] == 0:
        if c[i][1] == 'AC':
            aclist[c[i][0]] += 1
            AC += 1
        else:
            WA += 1
print(AC, WA)

### FIXED CODE ###

n, m = map(int, input().split())
c = [input().split() for i in range(m)]
for i in range(m):
    c[i][0] = int(c[i][0])
AC, WA = 0, 0
acwa = [[0, 0] for i in range(n)]
for i in range(m):
    if acwa[c[i][0] - 1][0] == 0:
        if c[i][1] == 'AC':
            acwa[c[i][0] - 1][0] += 1
            AC += 1
            WA += acwa[c[i][0] - 1][1]
        else:
            acwa[c[i][0] - 1][1] += 1

print(AC, WA)
n = int(input())
s = input()

def inverse(b, w, index, first):
    if first == '#':
        count = b[index//2 + 1] + w[-1] - w[(index + 1)//2]
    else:
        count = b[(index+1)//2] + w[-1] - w[index//2 + 1]
    return count

num = []
first = s[0]
end = s[-1]
pre = first
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        num.append(count)
        count = 1
        pre = c
num.append(count)

b = [0]
w = [0]
offset = 0
bsum = 0
wsum = 0
if first == '*':
    offset = 1
for i in range(len(num)):
    if i % 2 == offset:
        bsum += num[i]
        b.append(bsum)

offset = abs(offset -1)
for i in range(len(num)):
    if i % 2 == offset:
        wsum += num[i]
        w.append(wsum)

if len(num) == 1:
    print(0)
else:
    minlist = []
    minlist.append(sum(num[::2]))
    minlist.append(sum(num[1::2]))
    for i in range(len(num)):
        minlist.append(inverse(b, w, i, first))
    print(min(minlist))



### FIXED CODE ###

n = int(input())
s = input()

num = []
first = s[0]
end = s[-1]
pre = first
count = 0
for c in s:
    if c == pre:
        count += 1
    else:
        num.append(count)
        count = 1
        pre = c
num.append(count)

if len(num) == 1:
    print(0)
else:
    b = 0
    w = n
    offset = 0
    if first == '#':
        offset = 1
    w = sum(num[offset::2])
    minlist = [b + w]
    for i in range(len(num)):
        if i % 2 == offset:
            w -= num[i]
        else:
            b += num[i]
        minlist.append(b + w)
    print(min(minlist))
S = input()
for i in range(1,5):
  if S[i] == S[i-1]:
    print('Bad')
    break


### FIXED CODE ###

S = input()
for i in range(1,4):
  if S[i] == S[i-1]:
    print('Bad')
    break
else:
  print('Good')
n=int(input())
d=map(int,input().split())
m=n/2
d=sorted(d)
print(d[m+1]-d[m])

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(n/2)
d=sorted(d)
print(d[m]-d[m-1])
import sys
from collections import defaultdict, deque
readline = sys.stdin.readline

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    deg[a] += 1
    deg[b] += 1


def dist_3(i):
    q = deque([i])
    pair = []
    for a in G[i]:
        for b in G[a]:
            for c in G[b]:
                pair.append(c)
    return pair


ans = list(range(1, n+1))
idx = sorted(range(n), key=lambda x:deg[x])
for i in range(n//3):
    ans[idx[i]], ans[(i+1)*3] = ans[(i+1)*3], ans[idx[i]]
print(*ans)


### FIXED CODE ###

import sys
from collections import defaultdict, deque
readline = sys.stdin.readline

inf = 10 ** 5
n = int(readline())
G = defaultdict(list)
deg = [0] * n
for _ in range(n-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

q = deque([0])
depth = [-1] * n
depth[0] = 0
d = 1
while q:
    x = q.popleft()
    d = depth[x] + 1
    for y in G[x]:
        if depth[y] == -1:
            q.append(y)
            depth[y] = d
r0 = list(range(3, n + 1, 3))
r1 = list(range(1, n + 1, 3))
r2 = list(range(2, n + 1, 3))
odd = [i for i in range(n) if depth[i] % 2]
even = [i for i in range(n) if not depth[i] % 2]
if len(even) <= n // 3:
    odd, even = even, odd
if len(odd) <= n // 3:
    r = r2 + r1 + r0
else:
    r = r1 + r0 + r2
ans = [0] * n
for i in odd:
    ans[i] = r.pop()
for i in even:
    ans[i] = r.pop()
# print(f'{even=}{odd=}{num=}')
print(*ans)
'''
ITP-1_4-C
 ?¨???????
???????????´??° a, b ??¨?????????????????? op ?????????????????§???a op b ????¨??????????????????°?????????????????????????????????
????????????????????? op ??????"+"(???)???"-"(???)???"*"(???)???"/"(???)???????????¨?????????????????§????????????????????´?????????
?°???°?????\??????????????¨????????????????¨????????????¨????????????
???Input
??\???????????°????????????????????????????§???????????????????????????????????????????????????¢????????\????????¨????????§??????
 a op b
op ??? '?' ?????¨??? ??\?????????????????????????????????????????±???????????????????????£????????????????????????
???Output
?????????????????????????????????????¨??????????????????????????????????????????????
'''
# import
import sys

# ?????°??????????????????
for inputData in sys.stdin:
    a, op, b = map(int,input().split())
    retVal = 0

    # 0?????´??? ????????????
    if op == '?':
        # exec end
        break
    elif op == '+':
        retVal = int(a) + int(b)
    elif op == '-':
        retVal = int(a) - int(b)
    elif op == '*':
        retVal = int(a) * int(b)
    elif op == '/':
        retVal = int(a) / int(b)
    else:
        retVal = 0

    # ????????????
    print(retVal)

### FIXED CODE ###

'''
ITP-1_4-C
 ?¨???????
???????????´??° a, b ??¨?????????????????? op ?????????????????§???a op b ????¨??????????????????°?????????????????????????????????
????????????????????? op ??????"+"(???)???"-"(???)???"*"(???)???"/"(???)???????????¨?????????????????§????????????????????´?????????
?°???°?????\??????????????¨????????????????¨????????????¨????????????
???Input
??\???????????°????????????????????????????§???????????????????????????????????????????????????¢????????\????????¨????????§??????
 a op b
op ??? '?' ?????¨??? ??\?????????????????????????????????????????±???????????????????????£????????????????????????
???Output
?????????????????????????????????????¨??????????????????????????????????????????????
'''
# import
import sys

# ?????°??????????????????
for inputData in sys.stdin:
    inputList = inputData.split()
    a, op, b = int(inputList[0]), inputList[1], int(inputList[2])
    retVal = 0

    # 0?????´??? ????????????
    if op == '?':
        # exec end
        break
    elif op == '+':
        retVal = a + b
    elif op == '-':
        retVal = a - b
    elif op == '*':
        retVal = a * b
    elif op == '/':
        retVal = a // b
    else:
        retVal = 0

    # ????????????
    print(retVal)
import math
N = int(input())
A = [int(i) for i in input().split()]

def mygcd(A):
    if len(A) == 1:
        return A[0]
    else:
        return math.gcd(A[0],mygcd(A[1:]))
        
ans = []
for i in range(N):
    ans.append(mygcd(A[:i-1]+A[i:]))

print(max(ans))

### FIXED CODE ###

from fractions import gcd
#input
N = int(input())
A = [int(i) for i in input().split()]
#cluc left and right gcd 
left = [0]*N
right = [0]*N
count = 0
left[0] = A[0]
right[-1] = A[-1]
Ans = []

for i in A[1:]:
    left[count+1] = gcd(left[count],i)
    count += 1

for i in reversed(A[:-1]):
    right[count-1] = gcd(right[count],i)
    count -= 1
# make ans
Ans.append(right[1])
Ans.append(left[-2])
for i in range(N-2):
    Ans.append(gcd(left[i],right[i+2]))
print(max(Ans))
print((int(input())+1)//2)

### FIXED CODE ###

h, a = map(int, input().split())
c = 0
while  h > 0:
    h-=a
    c+=1 
print(c)
import itertools
n = input()
x, pm, a = [], [1,-1], 7-int(n[0])
for i in range(1,4):
	x.append(int(n[i]))
for j in itertools.product(pm,repeat=3):
	if x[0]*j[0]+x[1]*j[1]+x[2]*j[2]==a:
		y = list(j)
		break
for k in range(3):
	if y[k]==1: y[k] = "+"
	else: y[k] = "-"
print(n[0]+y[0]+n[1]+y[1]+n[2]+y[2]+n[3]+"=7")

### FIXED CODE ###

n = input()
if n[1]==n[2]:
	if n[0]==n[1] or n[2]==n[3]:
		print("Yes")
	else:
		print("No")
else: print("No")
a, b, k = (int(x) for x in input().split())
c = max(a, b)
l = [1]
for i in range(2, int(c/2)+1):
    if a % i == 0 and b % i == 0: l.append(i)
print(l[-k])

### FIXED CODE ###

a, b, k = (int(x) for x in input().split())
l = [i for i in range(1, min(a, b)+1) if a % i == 0 and b % i == 0]
print(l[-k])
n,k,x,y=map(int,input().split())

if n>k:
  print(round(k*x+(n-k)*y)
        
else:
        print(round(k*x)
        

### FIXED CODE ###

n = int(input())
k = int(input())
x= int(input())
y= int(input())

if n>k:
  print(k*x+(n-k)*y)

else:
  print(n*x)
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

# もしすべてaから選んだ場合
time = k
aOnly = 0
for i in range(len(a)):
    time -= a[i]
    if time < 0:
        time += a[i]
        break
    aOnly += 1
a_idx = i-1
b_idx = -1
if time > 0:
    for i in range(len(b)):
        time -= b[i]
        if time < 0:
            break
        aOnly += 1
    b_idx = i-1
    ans = aOnly
    time += b[i]

else:
    ans = aOnly
    time += a[i]

ans_kari = ans
for i in range(a_idx, -1, -1):
    time += a[i]
    ans_kari -= 1
    for j in range(b_idx+1, len(b)):
        time -= b[i]
        if time < 0:
            time += b[i]
            b_idx = i-1
            break
        ans_kari += 1
    ans = max(ans, ans_kari)
    
print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ans = 0

# もしすべてaから選んだ場合
time = k
aOnly = 0
for i in range(len(a)):
    time -= a[i]
    if time < 0:
        time += a[i]
        i -= 1
        break
    aOnly += 1
a_idx = i
b_idx = -1

for i in range(len(b)):
    time -= b[i]
    if time < 0:
        time += b[i]
        i -= 1
        break
    aOnly += 1
b_idx = i
ans = aOnly

ans_kari = ans
for i in range(a_idx, -1, -1):
    time += a[i]
    ans_kari -= 1
    for j in range(b_idx+1, len(b)):
        time -= b[j]
        if time < 0:
            time += b[j]
            b_idx = j-1
            break
        ans_kari += 1
    ans = max(ans, ans_kari)
    
print(ans)
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs.copy()
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)


### FIXED CODE ###

import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)
#python 3.7.1

a=int(input())

b=int(input())

c=int(input())

d=int(input())

cnt=0

while(d!=0):

  

  if(a!=0 and d>0):

    d-=1

    a=a-1

    

    cnt=cnt+1

    

  elif b!=0 and d>0:

    d-=1

    b=b-1

    

    

  elif c!=0 and d>0:

    d-=1

    c=c-1

    

    cnt=cnt-1

    

print(cnt)

  

### FIXED CODE ###

#python 3.7.1

a, b, c, d=map(int, input().split())

k=d

if(a-k>0):

  print(k)

else:

  k=d-a

  if(b-k>0):

    print(a)

    

  else:

    k=d-a-b

    print(a-k)
import math
T = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
x = (A[0]-B[0])*T[0]
y = (B[0]-A[0])*T[0] + (B[1]-A[1])*T[1]

if x < 0:
    x *= -1
    y *= -1

ans = -(-x//y)*2-1
if x%y == 0:
    ans -= 1
print(ans)

### FIXED CODE ###

T1, T2 = map(int,input().split())
A1, A2 = map(int,input().split())
B1, B2 = map(int,input().split())

A1 *= T1
B1 *= T1
A2 *= T2
B2 *= T2

if A1+A2 > B1+B2: # Aを遅く
    A1,B1 ,A2,B2 = B1,A1 ,B2,A2

if A1+A2 == B1+B2:
    print("infinity")
    exit()

if A1 < B1:
    print(0)
    exit()

def nibu(l,r):
    if l >= r:
        return l
    c = (l+r+1)//2
    if (A1+A2)*(c-1)+A1 >= (B1+B2)*(c-1)+B1:
        return nibu(c,r)
    else:
        return(nibu(l,c-1))

ans = nibu(0,10**100)
if (A1+A2)*(ans-1)+A1 == (B1+B2)*(ans-1)+B1:
    print(ans*2-2)
else:
    print(ans*2-1)
N = input()
X = []
U = []
for i in range(N):
    (x, u) = int(input().split())
    X[i] = x
    U[i] = u

otoshidama = 0.0

for i in range(N):
    if U[i] == "JPY":
        otoshidama += X[i]
    elif U[i] == "BTC":
        otoshidama += X[i] * 380000.0

print(otoshidama)

### FIXED CODE ###

N = int(input())
X = []
U = []
for i in range(N):
    I = input().split()
    (x, u) = (float(I[0]), I[1])
    X.append(x)
    U.append(u)

otoshidama = 0.0

for i in range(N):
    if U[i] == "JPY":
        otoshidama += X[i]
    elif U[i] == "BTC":
        otoshidama += X[i] * 380000.0

print(otoshidama)
age = int(input())
fee = int(input())

if age > 13:
	print(fee)
    
elif 6 <= age <= 12:
	print(fee / 2)

else:
	print(0)

### FIXED CODE ###

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

if A >= 13:
	print(B)
    
elif 6 <= A <= 12:
	print(B // 2)

else:
	print(0)
n,m=map(int, input().split())
a=list(map(int, input().split()))

a.sort(reverse=True)
b=sum(a)/4/m
print(a)
print(a[m])
if a[m-1]<b:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

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

a.sort(reverse=True)
b=sum(a)/4/m
if a[m-1]<b:
    print('No')
else:
    print('Yes')
c = [0,2,5,5,4,5,6,3,7,6]
N, M = list(map(int, input().split()))
A = list(map(int, input().split()))

B = [0] * M
for i in range(M):
    B[i] = c[A[i]]

x = min(B)
value = 0
for i in range(M):
    if B[i] == x:
        value = max(A[i], value)
y = N % x
if y == 0:
    print(str(value) * (N / x))
else:
    k = 10
    for i in range(M):
        if B[i] % x == y:
            if k > B[i]:
                k = B[i]
                l = A[i]
            elif k == B[i]:
                l = max(l, A[i])
    if value > l:
        print(str(value) * ((N - k) // x) + str(l))
    else:
        print(str(l) + str(value) * ((N - k) // x))

### FIXED CODE ###

def f(x):
    k = int(x)
    return c[k], k


c = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
N, M = list(map(int, input().split()))
A = list(map(f, input().split()))
A = sorted(A, key=lambda x: x[0] * 10 - x[1])

# 数字を作成するのに必要なマッチ数のリストを作成
b = []
dic = {}
n = 0
for d in A:
    if n != d[0]:
        b.append(d[0])
        n = d[0]
        dic[n] = d[1]

ans = [0] * b[0]
n = b[0]
while True:
    max_ = 0
    for d in b:
        if n - d == 0:
            if dic[d] > max_:
                max_ = dic[d]
        elif n - d > 0 and ans[n - d] > 0:
            t = ans[n - d] * 10 + dic[d]
            max_ = max(max_, t)

    if n == N:
        print(max_)
        break
    ans.append(max_)
    n += 1
import numpy as np

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

print(int((a * b) / np.gcd(a, b)))


### FIXED CODE ###

import fractions

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

print(int((a * b) / fractions.gcd(a, b)))
#!/usr/bin/python3
# -*- coding: utf-8 -*-
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def list_euclid(int_list):
    ans = int_list[0]
    for i in range(1,len(int_list)):
        ans = euclid(ans, int_list[i])
        if ans == 1:
            return ans
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
max = 0
b_int = 0
if n < 10:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      # a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      x = list_euclid(a)
      if max < x:
        max = x
      a.append(p)
else:
  for i in range(0,n):
    if b_int == a[0]:
      p = a.pop(0)
      # a.append(p)
    else:
      p = a.pop(0)
      b_int = p
      k = len(a) // 2
      x = 0
      y = list_euclid(a[0:k])
      if y == 1:
        x = 1
      else:
        z = list_euclid(a[k:n-1])
        x = euclid(y, z)
      if max < x:
        max = x
      a.append(p)
print(max)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import sys
def gcd(a, b): #最大公約数
  while b:
    a, b = b, a % b
  return int(a)
    
n = int(input())
a = list(map(int, input().split()))
if n==2:
  print(max(a))
  sys.exit(0)
elif n==3:
  lis = [gcd(a[0], a[1]), gcd(a[1], a[2]), gcd(a[2], a[0])]
  print(max(lis))
  sys.exit(0)
tmp_unused = gcd(a[0], a[1])
tmp_used = max(a[0], a[1])
#print("used=", tmp_used, "unused=", tmp_unused)
for i in range(2,n):
  #print(a[i])
  tmp_used = max(tmp_unused, gcd(tmp_used, a[i]))
  tmp_unused = gcd(tmp_unused, a[i])
  
  #print("used=", tmp_used, "unused=", tmp_unused)
print(tmp_used)
import sys
import random
import bisect
from collections import deque

def cumsum(a):
    tmp = 0
    ret = []
    for i in range(len(a)):
        tmp += a[i]
        ret.append(tmp)
    return ret

#x = input().split()
#a = list(map(int, input().split()))
#b = list(map(int, input().split()))
#n, m, time = int(x[0]), int(x[1]), int(x[2])

#n, m = 100000, 100000
#time = 100000000
#a = list(random.choices(range(10000), k=n))
#b = list(random.choices(range(10000), k=m))

a_sum, b_sum = cumsum(a), cumsum(b)

ans, j = 0, M
for i in range(N + 1):
    if a_sum[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
        ans = max(ans, i + j)

print (ans)


### FIXED CODE ###

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

a, b = [0], [0]
for i in range(N): a.append(a[i] + A[i])
for i in range(M): b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
x=int(input())
c=1

for b in range(1,x):
  for p in range(2,x):
    if b**p<=x:c=max(c,b**p)
      else:break

print(c)

### FIXED CODE ###

x=int(input())
c=1

for b in range(1,x):
  for p in range(2,x):
    if b**p<=x:c=max(c,b**p)
    else:break

print(c)