Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n= int(input())
s=[input() for i in range(n)]

ss = set(s)
ans = 0
ma = 0
li = []
for i in ss:
    ans = s.count(i)
    if(ans==ma):
        li.append(i)
    if(ans>ma):
        ma = ans
        li = [i]

li.sort()


if(len(li)==1):
    print(li[0])
else:
    for i in li:
        print(i)

### FIXED CODE ###

import collections

n= int(input())
s=[input() for i in range(n)]

li = collections.Counter(s)
ma= max(li.values())

ans= [i for i,j in li.items() if(j==ma)]
print("\n".join(sorted(ans)))
### BUGGY CODE ###

N,T = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: (x[0],x[1]))

# dp[i][j]: 満足度の最大値
# i: i品目まで
# j: 制限時間(< T)
dp = [[0] * 3100 for _ in range(3100)]

dp[0][0] = 0

# 貰うDP
ans = 0
for i in range(1, N + 1):
    for j in range(T):
        dp[i][j] = dp[i - 1][j]
        
        # ラストオーダーはAB[i - 1]
        ans = max(ans, dp[i][j] + AB[i - 1][1])

        if j - AB[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

print(ans)

### FIXED CODE ###

def main():
    N,T = map(int, input().split())
    AB = [[int(i) for i in input().split()] for _ in range(N)]

    AB.sort()

    # dp[i][j]: 満足度の最大値
    # i: i品目まで
    # j: 制限時間(< T)
    dp = [[0] * 3100 for _ in range(3100)]

    dp[0][0] = 0

    # 貰うDP
    ans = 0
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]
            
            # ラストオーダーはAB[i - 1]
            ans = max(ans, dp[i][j] + AB[i - 1][1])

            if j - AB[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - AB[i - 1][0]] + AB[i - 1][1])

    print(ans)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))

L.sort()

ans=0
for i in range(N-1):
    for j in range(i+1,N):
        temp=L[i]+L[j]
        for k in range(N):
            f=True
            if k!=i and k!=j:
                if temp<=L[k]:
                    break
                elif L[j]+L[k]<=L[i]:
                    f=False
                elif L[k]+L[i]<=L[j]:
                    f=False
                if f:
                    ans+=1


print(ans//3)



### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int,input().split()))

L.sort()

ans=0
for i in range(N-1,-1,-1):
    for j in range(i-1,-1,-1):
        temp=L[i]-L[j]
        idx=bisect.bisect_right(L,temp)
        ans+=max(0,j-idx)
print(ans)
### BUGGY CODE ###

import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))

    for j in range(K+1):
        if j-a-1>=0:
            NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod
        else:
            NEXT[j]=NOWSUM[j]%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])
### BUGGY CODE ###

N = int(input())
A = [None]*N
for i in range(N):
  A[i] = list(map(int,input().split()))
A.sort(key = lambda x:x[1])
B = [0]*len(A)
C = [0]*len(A)
for b in range(len(A)):
  B[b] = A[b][0]
for c in range(len(A)):
  C[c] = A[c][1]
jud = 'Yes'
for j in range(N):
  if sum(B[:j+1]) > C[j]:
    jud = 'No'
    #print(C[j])
    #print(B[:j+1])
print(jud)

### FIXED CODE ###

N = int(input())
A = [None]*N
for i in range(N):
  A[i] = list(map(int,input().split()))
A.sort(key = lambda x:x[1])
B = [0]*len(A)
C = [0]*len(A)
for b in range(len(A)):
  B[b] = A[b][0]
for c in range(len(A)):
  C[c] = A[c][1]
jud = 'Yes'
Sum = 0
for j in range(N):
  Sum += B[j]
  if Sum > C[j]:
    jud = 'No'
    #print(C[j])
    #print(B[:j+1])
print(jud)
### BUGGY CODE ###

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

limit = 10 ** 18
current = 1

maxFlag = False

for x in range(N):
    current *= A[x]

if current > limit:
    print(-1)
else:
    print(current)


### FIXED CODE ###

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

rev_A = sorted(A, reverse=True)

if 0 in rev_A:
    print(0)
    exit()
else:
    limit = 10 ** 18
    current = 1

    for x in range(N):
        current *= rev_A[x]

        if current > limit:
            print(-1)
            exit()
    print(current)
### BUGGY CODE ###

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

id_set = set(range(N + 1))

for m in range(M):
  L, R = map(int, input().split())
  id_set = id_set & set(range(L, R + 1, 1))
  if len(id_set) == 0:
    break


print(len(id_set))

### FIXED CODE ###

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

L = list(range(M))
R = list(range(M))

for m in range(M):
  L[m], R[m] = map(int, input().split())

L_max = max(L)
R_min = min(R)

print(R_min - L_max + 1 if L_max <= R_min else 0)
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())
for i in range(q):
    x,y,z = input().split()
    if x == "1":
        s[int(y)-1] = z
    else:
        
        print(len(set(s[int(y)-1:int(z)])))

### FIXED CODE ###

import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
        s[int(y)-1] = z
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
T = [[] for i in range(N+1)]
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[a].append(b)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p):
    global T,V
    for c in T[v]:
        if c==p:continue
        V[c]+=V[v]
        f(c,v)
f(1,0)
print(*V[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
T = [0]*(N+1)
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[b] = a
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
for i in range(1,N+1):
    V[i]+=V[T[i]]
print(*V[1:])
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
s = input()

dp = [defaultdict(int), defaultdict(int)]

dp[0][""] = 1
for i in range(n):
    dp[(i + 1) % 2] = dp[i % 2].copy()
    for j in dp[i % 2]:
        # dp[(i + 1) % 2][j] = dp[i % 2][j]
        if len(j) < 3:
            dp[(i + 1) % 2][j + s[i]] += dp[i % 2][j]

ans = 0
for j in dp[n % 2]:
    if len(j) == 3:
        # print(j)
        ans += 1

print(ans)


### FIXED CODE ###

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

dp = [set(), set()]

dp[0].add("")
for i in range(n):
    dp[(i + 1) % 2] = dp[i % 2].copy()
    i1 = (i + 1) % 2
    i0 = (i + 0) % 2
    for j in dp[i0]:
        if len(j) < 3:
            dp[i1].add(j + s[i])

ans = 0
for j in dp[n % 2]:
    if len(j) == 3:
        # print(j)
        ans += 1

print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
#res = A[0]
for i in range(1,N): 
	A[0] *= A[i]
if A[0] <= 10**18:
	print(A[0])
else:
	print("-1")


### FIXED CODE ###

a=int(input())
b=input().split(" ")
sum1=1
 
if "0" in b:
    print("0")
else:
    for i in range(a):
        sum1=sum1*int(b[i])
        if sum1>10**18:
            sum1=-1
            break
    print(sum1)
### BUGGY CODE ###

a=[]
def asff(b,a,n):
    asum=0
    for j in range(n):
        asum=asum+abs(a[j]-(b+j+1))
    return asum    

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

amin=min(a)-n
amax=max(a)+n

#asmin=amax*n
#for i in range(amin,amax+1):
#    asf=asff(i,a,n)
#    if asf<asmin:
#        asmin=asf

ast=min(a)-n
aed=max(a)+n
asst=asff(ast,a,n)
ased=asff(aed,a,n)

icnt=0
while ast+1<=aed:    
    amed=(ast+aed)//2
    if asst>ased:
        ast=amed
        asst=asff(ast,a,n)
    else:
        aed=amed
        ased=asff(aed,a,n)
    icnt=icnt+1
    if icnt>10000:
        break              
    
print(ased)


### FIXED CODE ###

import bisect

a=[]
s=[]
def asff(a,b,s,n):
    m=bisect.bisect(a,b)
    if m<=0:
        asf=-n*b+s[n-1]
    elif m<n:
        asf=(2*m-n)*b+s[n-1]-2*s[m-1]
    elif n<=m:
        asf=n*b-s[n-1]
    return asf

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

#n=5
#stra="2 2 3 5 5"
#ans=2

#n=9
#stra="1 2 3 4 5 6 7 8 9"
#ans=0

#n=6
#stra="6 5 4 3 2 1"
#ans=18

#n=7
#stra="1 1 1 1 2 3 4"
#ans=6

#a=list(map(int,stra.split()))

for i in range(n):
    a[i]=a[i]-i-1
#print(a)
a.sort()

s=[a[0]]
for i in range(1,n):
    s.append(s[i-1]+a[i])
    
bmin=min(a)-n
bmax=max(a)+n

b1=bmin
b5=bmax+1
b2=b1+int((b5-b1)/4)
b3=b1+int((b5-b1)/2)
b4=b1+int((b5-b1)/4*3)
#b2=b1+(b5-b1)//4
#b3=b1+(b5-b1)//4*2
#b4=b1+(b5-b1)//4*3
#print("b1",b1,"b5",b5)
    
asmin=bmax*n
#m0=0
m1=bisect.bisect(a,bmin)


while b1+1<b5:
    c=[]
    c.append([asff(a,b1,s,n),b1])
    c.append([asff(a,b2,s,n),b2])
    c.append([asff(a,b3,s,n),b3])
    c.append([asff(a,b4,s,n),b4])
    c.append([asff(a,b5,s,n),b5])
    c.sort()
    asf=c[0][0]
    d=[]
    d.append(c[0][1])
    d.append(c[1][1])
    d.append(c[2][1])
    d.sort()
    b1=d[0]
    b5=d[2]
    b2=b1+int((b5-b1)/4)
    b3=b1+int((b5-b1)/2)
    b4=b1+int((b5-b1)/4*3)
    
#    print("b1",b1,"b5",b5,"d0",d[0],"asf",asf)
    if asf<asmin:
        asmin=asf

print(asmin)
### BUGGY CODE ###

S = int(input())
listS = list(str(S))
l = len(listS)
dp = int(listS[-1])
suml = [dp]
for i in range(l-1):
    dp = dp + pow(10,(i+1))*int(listS[-2-i])
    suml.append(dp % 2019)
mod = {0:1}
for a in suml:
    if a in mod.keys():
        mod[a] += 1
    else:
        mod[a] = 1
cnt = 0
for a in mod:
    if mod[a] > 1:
        cnt += (mod[a]*(mod[a]-1))//2
print(cnt)

### FIXED CODE ###

S = str(input())
l = len(S)
mod = [0] * 2019
dp = 0
pw = 1
for i in range(l):
    mod[dp % 2019] += 1
    dp = dp + pw * int(S[-1-i])
    pw = (pw * 10) % 2019
mod[dp % 2019] += 1
cnt = 0
for i in range(2019):
    cnt += (mod[i]*(mod[i]-1))//2
print(cnt)
### BUGGY CODE ###

a=input().split(" ")

number1=int(a[0])
number2=int(a[1])
n1=0
n2=0

for i in range(number1+1):
    for j in range(number1+1):
        n1=number2-int(i)-int(j)
        if n1<=number1 and 0<=n1:
            n2=n2+1

print(n2)

	


### FIXED CODE ###

a=input().split(" ")

number1=int(a[0])
number2=int(a[1])
n1=0
n2=0

for i in range(number1+1):
    for j in range(number1+1):
        n1=number2-int(i)-int(j)
        if n1<=number1 and 0<=n1:
            n2=n2+1

print(n2)
### BUGGY CODE ###

def cmb(a, b, m=998244353):
    if (b > a - b):
        return cmb(a, a - b, m)
    c = d = 1
    for i in range(b):
        c *= (a - i)
        d *= (b - i)
        c %= m
        d %= m
    return c * pow(d, m - 2, m) % m


def resolve():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    for i in range(k + 1):
        ans += cmb(n - 1, i) * pow(m - 1, n - i - 1, mod)
    ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

class Combination:

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


def resolve():
    n, m, k = map(int, input().split())
    mod = 998244353
    c = Combination(n, mod)
    ans = 0
    for i in range(k + 1):
        ans += c(n - 1, i) * pow(m - 1, n - i - 1, mod)
    ans %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    x = 1
    for i in a:
        x *= i
    if x > 1000000000000000000:
        print(-1)
        return
    print(x)
main()

### FIXED CODE ###

def main():
    N =int(input())
    A =list(map(int,input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main()
### BUGGY CODE ###

"""E."""

import math
import sys
from typing import List


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


RESULT_A = 'pairwise coprime'
RESULT_B = 'setwise coprime'
RESULT_C = 'not coprime'

n = int(input())

a_list = list(map(int, input().split(' ')))


def get_all_gcd(l: List[int]) -> List[int]:
    result = []
    for i, v1 in enumerate(l[:-1]):
        for v2 in l[i + 1:]:
            result.append(math.gcd(v1, v2))
    return result


gcds = get_all_gcd(a_list)

if [1] * len(gcds) == gcds:
    print(RESULT_A)
    exit(0)

if [1] * len(gcds) == get_all_gcd(gcds):
    print(RESULT_B)
    exit(0)

print(RESULT_C)


### FIXED CODE ###

"""E."""

import sys


def input() -> str:  # noqa: A001
    """Input."""
    return sys.stdin.readline()[:-1]


RESULT_TEXT = {
    1: 'pairwise coprime',
    2: 'setwise coprime',
    3: 'not coprime',
}

n = int(input())

a_list = list(map(int, input().split(' ')))

ans = 0

MAX = 1000000 + 1
counts = [0] * MAX
for a in a_list:
    counts[a] += 1

max_count = 0

for i in range(2, MAX):
    max_count = max(max_count, sum(counts[i::i]))

if max_count == n:
    ans = 3
elif max_count >= 2:
    ans = 2
else:
    ans = 1

print(RESULT_TEXT[ans])
### BUGGY CODE ###

import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1.7):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()


### FIXED CODE ###

import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()
### BUGGY CODE ###

MOD = 10**9 + 7

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

dp = [1] * (N+1)

if 1 in A: dp[1] = 0

for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % MOD
    
print(dp[N])

### FIXED CODE ###

MOD = 10**9 + 7

N, M = map(int,input().split())
A = set()
for _ in range(M):
    A.add(int(input()))

dp = [1] * (N+1)

if 1 in A:
    dp[1] = 0

for i in range(N-1):
    if i+2 in A:
        dp[i+2] = 0
    else:
        dp[i+2] = (dp[i] + dp[i+1]) % MOD
    
print(dp[N])
### BUGGY CODE ###

n, c = map(int, input().split())
sushi = []
for i in range(n):
    x, v = map(int, input().split())
    sushi.append((x, v))
sushi.sort()
sushi_reversed = list(reversed([(c - x, v) for x, v in sushi]))


# def solve(s, sr):
#     d = 0
#     v = 0
#     v_d_max = (0, 0)
#     v_2d_max = (0, 0)
#     conds = []

#     for x_i, v_i in s:
#         v = v + v_i - (x_i - d)
#         d = x_i
#         v_d_max = max(v_d_max, (v, d))
#         if v - d > v_2d_max[0]:
#             v_2d_max = (v - d, d)
#             conds.append((v - d, d))
#     return v_d_max, v_2d_max, conds

def solve(s, sr):
    d = 0
    v = 0
    v_2d_max = 0
    v_max = 0
    n = len(s)
    for i in range(n):
        x_i, v_i = s[i]
        v = v + v_i - (x_i - d)
        d = x_i
        v_max = max(v_max, v)
        if v - d > v_2d_max:
            v_2d_max = v - d
            v_sub = sub_solve(sr[:n - 1 - i])
            v_max = max(v_max, v_2d_max + v_sub)
    return v_max


def sub_solve(s):
    d = 0
    v = 0
    v_max = 0

    for x_i, v_i in s:
        v = v + v_i - (x_i - d)
        d = x_i
        v_max = max(v_max, v)
    return v_max

# l_v_d_max, l_v_2d_max, l_conds = solve(sushi, sushi_reversed)
# r_v_d_max, r_v_2d_max, r_conds = solve(sushi_reversed, sushi)
# print(l_v_d_max, l_v_2d_max, l_conds, r_v_d_max, r_v_2d_max, r_conds)

# max_v = max(l_v_d_max[0], r_v_d_max[0])
# if l_v_d_max[1] + r_v_2d_max[1] < c:
#     max_v = max(max_v, l_v_d_max[0] + r_v_2d_max[0])
# else:
#     for v, d in r_conds:
#         if l_v_d_max[1] + d < c:
#             max_v = max(max_v, l_v_d_max[0] + v)

# if l_v_2d_max[1] + r_v_d_max[1] < c:
#     max_v = max(max_v, l_v_2d_max[0] + r_v_d_max[0])
# else:
#     for v, d in l_conds:
#         if d + r_v_d_max[1] < c:
#             max_v = max(max_v, v + r_v_d_max[0])

# print(max_v)

# l_v_d_max, l_v_2d_max, l_conds = solve(sushi, sushi_reversed)
# r_v_d_max, r_v_2d_max, r_conds = solve(sushi_reversed, sushi)
# print(max_v)


l = solve(sushi, sushi_reversed)
r = solve(sushi_reversed, sushi)
print(max(solve(sushi, sushi_reversed), solve(sushi_reversed, sushi)))


### FIXED CODE ###

n, c = map(int, input().split())
sushi = []
for i in range(n):
    x, v = map(int, input().split())
    sushi.append((x, v))
sushi.sort()
sushi_reversed = list(reversed([(c - x, v) for x, v in sushi]))


def accum_max(s):
    v = 0
    res = [(0, 0)]
    for x_i, v_i in s:
        v += v_i
        res.append(max(res[-1], (v-x_i, x_i)))
    return res[1:]


max_sushi = accum_max(sushi)
max_sushi_reversed = accum_max(sushi_reversed)


def solve(s, msr):
    v_max = 0
    v_2d_max = 0
    v = 0
    n = len(s)
    for i in range(n-1):
        x_i, v_i = s[i]
        v += v_i
        if v - x_i*2 > v_2d_max:
            v_2d_max = v - x_i*2
            v_sub = msr[n - 2 - i][0]
            v_max = max(v_max, v_2d_max + v_sub)
    return v_max


l = solve(sushi, max_sushi_reversed)
r = solve(sushi_reversed, max_sushi)
print(max(l, r, max_sushi[-1][0], max_sushi_reversed[-1][0]))
### BUGGY CODE ###

#import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())

    c = [0]*(K+1)
    def comb(k):
        if k == 0:
            ans = 1
        else:
            ans = c[k-1]*(N-k)//k
        c[k] = ans
        return ans

    ans = 0
    for k in range(K+1):
        ans += (comb(k)*M*pow(M-1, N-k-1, 998244353))%998244353

    print(ans%998244353)

main()


### FIXED CODE ###

#import numpy as np
import math
#from decimal import *
#from numba import njit
#@njit
def main():
    (N, M, K) = map(int, input().split())
    MOD = 998244353
    
    fact = [1]*(N+1)
    factinv = [1]*(N+1)
    for i in range(1,N+1):
        fact[i] = fact[i-1]*i % MOD
        factinv[i] = pow(fact[i], MOD-2, MOD)
    def comb(n, k):
        return fact[n] * factinv[k] * factinv[n-k] % MOD

    ans = 0
    for k in range(K+1):
        ans += (comb(N-1,k)*M*pow(M-1, N-k-1, MOD))%MOD

    print(ans%MOD)

main()
### BUGGY CODE ###

N = int(input())
sticks = list(map(int, input().split()))
sticks.sort()
ans = 0
for a in range(N-2):
  A = sticks[a]
  for b in range(a+1, N-1):
    B = sticks[b]
    for c in range(b+1, N):
      C = sticks[c]
      if A + B > C:
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
#print(L)
ans = 0
def find(x, arr):
  a = len(arr)//2
  cur = a
  while True:
    a //= 2
    if arr[cur] < x:
      if cur == len(arr)-1:
        return cur+1
      elif arr[cur+1] >=x:
        return cur+1
      else:
        cur += max(1,a)
    else:
      if cur == 0:
        return 0
      else:
        cur -= max(1, a)
for i in range(N-2):
  for j in range(i+1, N-1):
    ans += find(L[i] + L[j], L)-j-1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ov = 10**9+7
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
l = lcm(a)
def d(n):
  return l//n%ov
b= list(map(d,a))
print(sum(b)%ov)

### FIXED CODE ###

def main():
  from functools import reduce
  from fractions import gcd
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  ov = 10**9+7
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b)
  for i in range(n):
    ans += l//b[i]
  print(ans%ov)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import math

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

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)


### FIXED CODE ###

import math

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

DP = [[math.inf] * 100001 for _ in range(N+1)]
DP[0][0] = 0
for i in range(1, N+1):
    w, v = map(int, input().split())
    for j in range(100001):
        if j >= v:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-v]+w)
        else:
            DP[i][j] = DP[i-1][j]

ans = 100000
while DP[N][ans] > W:
    ans -= 1
print(ans)