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

N = int(input())

num = []
for i in range(N):
  num.append(int(input()))
  
ans = [min(num)]
num.remove(min(num))

for i in range(len(num)-1):
  if i % 4 == 0:
    m = max(num)
    ans.append(m)
    num.remove(m)
  elif i % 4 == 1:
    m = max(num)
    ans = [m] + ans
    num.remove(m)
  elif i % 4 == 2:
    m = min(num)
    ans.append(m)
    num.remove(m)
  else:
    m = min(num)
    ans = [m] + ans
    num.remove(m)

answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)

### FIXED CODE ###

from collections import deque
N = int(input())
 
num = []
for i in range(N):
  num.append(int(input()))
  
num = deque(sorted(num))
ans = deque([num.popleft()])
 
for i in range(N-2):
  if i % 4 == 0:
    ans.append(num.pop())
  elif i % 4 == 1:
    ans.appendleft(num.pop())
  elif i % 4 == 2:
    ans.append(num.popleft())
  else:
    ans.appendleft(num.popleft())

answer = max(abs(num[0]-ans[0]), abs(num[0]-ans[-1]))
for i in range(len(ans)-1):
  answer += abs(ans[i] - ans[i+1])
  
print(answer)
### BUGGY CODE ###

N = int(input())

lnam = list()
lnum = list()

for i in range(N):
    s = input()
    if s in lnam:
        lnum[lnam.index(s)] += 1
    else:
        lnam.append(s)
        lnum.append(1)

lall = list(zip(lnam, lnum))
ldwn = sorted(lall, key=lambda x:x[1], reverse=True)

lwin = list()
i = 0
while i != len(ldwn) and ldwn[i][1] == ldwn[0][1]:
    lwin.append(ldwn[i][0])
    i += 1

lans = sorted(lwin)
for j in range(len(lans)):
    print(lans[j])

### FIXED CODE ###

n = int(input())

d = {}

for i in range(n):
    s = input()
    d[s] = d.get(s, 0) + 1

m = max(d[i] for i in d)

for j in sorted(d):
    if d[j] == m:
        print(j)
### BUGGY CODE ###

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

v = []
for _ in range(K):
    L, R = map(int,input().split())
    # for d in range(L, R+1):
    #     moves.append(d)
    v.append((L, R))

dp = [0] * N        # マスi-1に到達するまでの操作列の個数
sdp = [0] * (N + 1) # dp[i]までの累積和 
dp[0] = 1
sdp[1] = 1

for n in range(1, N):
    for p in v:
        left = max(0, n - p[1])
        right = max(0, n - p[0]+1)
        dp[n] += sdp[right] - sdp[left]
    sdp[n+1] = sdp[n] + dp[n]

print(dp[-1] % mod)



### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
a = [int(x) for x in input().split()]

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        ans = (ans + a[i]*a[j]%MOD) % MOD

print(ans)

### FIXED CODE ###

MOD = 10**9+7
n = int(input())
a = [int(x) for x in input().split()]

s = sum(a)
ans = 0

for i in range(n):
    s -= a[i]
    ans = (ans + a[i]*s%MOD) % MOD

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

s = input()

# n = s.count("LR")
# print(n)
ans = []
while s.find("LR")!=-1:
    k = s.find("LR")
    t = s[:k+1]
    # print(t)
    a = [0]*len(s[:k+1])
    l = t.find("RL")
    # print(l)
    numR = t.count("R")
    # print(numR)
    numL = t.count("L")
    # print(numL)
    a[l] = (numR+1)//2 + (numL)//2
    a[l+1] = (numR)//2 + (numL+1)//2
    ans = ans + a
    # print(ans)
    s = s[k+1:]

# print(s)

a = [0]*len(s)
l = s.find("RL")
# print(l)
numR = s.count("R")
# print(numR)
numL = s.count("L")
# print(numL)
a[l] = (numR+1)//2 + (numL)//2
a[l+1] = (numR)//2 + (numL+1)//2
ans = ans + a
print(" ".join(list(map(str, ans))))

### FIXED CODE ###

s = input()
l = len(s)
ans = [0]*l
count = 0
for i in range(l):
    if s[i]=="R" and s[i+1]=="R":
        count += 1
    elif s[i]=="R" and s[i+1]=="L":
        count += 1
        ans[i] += (count+1)//2
        ans[i+1] += count//2
        count = 0
for i in reversed(range(l)):
    # print(i)
    # print(s[i])
    if s[i]=="L" and s[i-1]=="L":
        count += 1
    elif s[i]=="L" and s[i-1]=="R":
        count += 1
        ans[i] += (count+1)//2
        ans[i-1] += count//2
        count = 0
print(" ".join(map(str, ans)))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)


### FIXED CODE ###

import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*n
num=[]
if k>41:
    ans=[n]*n
    print(*ans)
else:
    def c(num1,num2,num3):
        num[max(0,num1-num2)]+=1
        num[min(num3,num1+num2+1)]-=1
    for i in range(k):
        num=[0]*(n+1)
        for j in range(n):
            c(j,a[j],n)
        num5=0
        for j in range(n):
            num5+=num[j]
            a[j]=num5
        if sum(a)==n*n:
            break
    print(*a)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
atai =abs(sum(a[0:1])-sum(a[1:]))
for i in range(N-1):
    h = abs(sum(a[:i+1])-sum(a[i+1:]))
    atai = min(h,atai)
print(atai)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = sum(a) - 2*a[0]
abst = abs(ans)
for i in range(1,N-1):
    ans -=2*a[i]
    if abs(ans)<abst:
        abst = abs(ans)
print(abst)
### BUGGY CODE ###

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

inv = [i for i in range(N-1)]
visited = [1]

path = [[] for i in range(N)]

for i in range(M):
  A, B = map(int, input().split())
  path[A-1].append(B)
  path[B-1].append(A)
nows = [1]
COUNTER = 0
for t in range(N):
  buf = []
  for now in nows:
    for p in set(path[now-1])-set(visited):
      inv[p-2] = now
      visited.append(p)
      buf.append(p)
      COUNTER+=1
  if len(buf) == 0:
    break
  nows = buf
  
print("Yes")
for i in inv:
  print(i)


### FIXED CODE ###

import queue

q = queue.Queue()
N, M = map(int, input().split())

ans = [-1 for i in range(N+1)]
path = [[] for i in range(N+1)]

for i in range(M):
  A, B = map(int, input().split())
  path[A].append(B)
  path[B].append(A)
q.put(1)
COUNTER = 0
while not q.empty() :
  now = q.get()
  for p in path[now]:
    if ans[p]==-1:
      ans[p]=now
      q.put(p)
      #print(COUNTER, now,p)
      COUNTER+=1
      
print("Yes")
for i in ans[2:]:
  print(i)
### BUGGY CODE ###

from collections import deque

s=deque(list( input() ))
t=deque([]) #

cnt=0

while s!=deque([]):
  x=s.popleft()
  if len(t)>=2 and x=="C":
    q=t.pop()
    p=t.pop()
    if p=="A" and q=="B":
      cnt += 1
      t.append("B")
      s.appendleft("A")
      s.appendleft("C")
    else:
      t.append(p)
      t.append(q)
      t.append(x)
      
  else:
    t.append(x)
        
#print(t,s)
print(cnt)

### FIXED CODE ###

from collections import deque

s=input()
s=s.replace("BC","D")
N=len(s)

cnt=0
cntA=0
cntD=0

for i in range(N):
  if s[i]=="A":
    cntA += 1
  elif s[i]=="D":
    cnt += cntA
  else:
    cntA=0
    cntD=0
    
print(cnt)
### BUGGY CODE ###

k, s = list(map(int, input().split()))
count = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        for z in range(0, k + 1):
            if (x + y + z == s):
                count+=1
print(count)


### FIXED CODE ###

k, s = list(map(int, input().split()))
count = 0
for x in range(0, k + 1):
    for y in range(0, k + 1):
        z = s - x - y
        if (0 <= z and z <= k):
            count+=1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    A = LI()

    B = [1] * N
    B[0] = A[0]
    for i in range(1, N):
        B[i] = B[i-1] * A[i]
    # print(B)

    B = [1] + B

    for i in range(K+1, N+1):
        tmp = B[i] / B[i-K]
        tmp2 = B[i-1] / B[i-1-K]
        # print(tmp, tmp2)
        if tmp > tmp2:
            print('Yes')
        else:
            print('No')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right

def solve():
    N, K = MI()
    A = LI()

    for i in range(K-1, N-1):
        b = A[i-K+1]
        f = A[i+1]
        if f > b:
            print('Yes')
        else:
            print('No')

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

import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10**9+7
 
def input():
    return sys.stdin.readline()[:-1]
 
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(10**5+10)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        x = S[-(i+1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x) # これしか選ぶ余地なし
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul *= 10 % 13
    print(dp[l][5]%MOD)
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
inf = sys.maxsize

n, k = map(int,input().split())
h = [int(i) for i in input().split()]

dp = [0] * n
dp[0] = 0
for i in range(1,n):
    if i < k:
        dp[i] = inf
        for j in range(1, i + 1):
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
    elif i >= k:
        dp[i] = inf
        for j in range(1, k + 1):
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
print(dp[n - 1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
inf = sys.maxsize

n, k = map(int,input().split())
h = [int(i) for i in input().split()]

dp = [0] * n
dp[0] = 0
for i in range(1,n):
    if i < k:
        dp[i] = inf
        for j in range(1, i + 1):
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
    elif i >= k:
        dp[i] = inf
        for j in range(1, k + 1):
            if dp[i - j] + abs(h[i] - h[i - j]) < dp[i]:
                dp[i] = dp[i - j] + abs(h[i] - h[i - j])
print(dp[n - 1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i+j<=n and (i>0 or j>0):
            v=b[i+j-1][0]
            pos=b[i+j-1][1]
            if i==0:
                dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
            elif j==0:
                dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
            else:
                dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)
### BUGGY CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())

flag = False
s = rr()
q = ri()
for _ in range(q):
    query = list(rs())
    if query[0] == '1':
        flag = not flag
        continue
    else:
        f = int(query[1])
        c = query[-1]
        if flag == True:
            if f == 1:
                s += c
            else:
                s = c+s
        else:
            if f == 1:
                s = c+s
            else:
                s += c
if flag:
    print(s[::-1])
else:
    print(s)            
















### FIXED CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())

flag = False
s = rr()
q = ri()
front = ''
end = ''
for _ in range(q):
    query = list(rs())
    if query[0] == '1':
        flag = not flag
        continue
    else:
        f = int(query[1])
        c = query[-1]
        if flag == True:
            if f == 1:
                end += c
            else:
                front = c+front
        else:
            if f == 1:
                front = c+front
            else:
                end += c
if flag:
    print((front+s+end)[::-1])
else:
    print(front+s+end)
### BUGGY CODE ###

import itertools
N=int(input())
d=list(map(int,input().split()))
cnt=0
for i in itertools.combinations(d,3):
  if i[0]<i[1]+i[2] and i[1]<i[0]+i[2] and i[2]<i[0]+i[1]:
    cnt+=1
print(cnt)

### FIXED CODE ###

import bisect
N=int(input())
d=sorted(list(map(int,input().split())))
cnt=0
for i in range(N-1,1,-1):
  for j in range(i-1,0,-1):
    k=bisect.bisect_right(d,d[i]-d[j])
    if j-k>0:
      cnt+=j-k
print(cnt)
### BUGGY CODE ###

n=int(input())
b=list(map(int,input().split()))
a=b
condition=''
cnt=0
for i in range(n):
  if i == 0:
    if a[i]>0:
      condition='minus'
    else:
      condition='plus'
  elif condition == 'plus':
    condition='minus'
    if sum(a[0:i+1])<=0:
      cnt+=abs(sum(a[0:i+1]))+1
      a[i]+=abs(sum(a[0:i+1]))+1
  elif condition == 'minus':
    condition='plus'
    if sum(a[0:i+1])>=0:
      cnt+=abs(sum(a[0:i+1]))+1
      a[i]-=abs(sum(a[0:i+1]))+1

print(cnt)

### FIXED CODE ###

n=int(input())
b=list(map(int,input().split()))
a=b[:]

cnt=0
wa=0
condition='plus'
for i in range(n):
  wa+=a[i]
  if condition == 'plus':
    condition='minus'
    if wa<=0:
      cnt+=abs(wa)+1
      a[i]+=abs(wa)+1
      wa+=abs(wa)+1
  elif condition == 'minus':
    condition='plus'
    if wa>=0:
      cnt+=abs(wa)+1
      a[i]-=abs(wa)+1
      wa-=abs(wa)+1

cnt1=cnt
a=b[:]
cnt=0
wa=0
condition='minus'
for i in range(n):
  wa+=a[i]
  if condition == 'plus':
    condition='minus'
    if wa<=0:
      cnt+=abs(wa)+1
      a[i]+=abs(wa)+1
      wa+=abs(wa)+1
  elif condition == 'minus':
    condition='plus'
    if wa>=0:
      cnt+=abs(wa)+1
      a[i]-=abs(wa)+1
      wa-=abs(wa)+1

cnt2=cnt
print(min(cnt1,cnt2))
### BUGGY CODE ###

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0

i = 0
j = 1
k = 2

while i < n-2:
    while j < n-1:
        while k < n:
            if ll[i] + ll[j] <= ll[k]:
                break
            else:
                # print([ll[i], ll[j], ll[k]])
                k += 1
                ans += 1
        j += 1
        k = j + 1
    i += 1
    j = i + 1
    k = j + 1

print(ans)


### FIXED CODE ###

n = int(input())
ll = list(map(int, input().split()))
ll.sort(reverse=True)

ans = 0

for i in range(n-2):
    j = i + 1
    k = n - 1
    while k > j:
        if ll[i] < ll[j] + ll[k]:
            ans += k - j
            j += 1
        else:
            k -= 1

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

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = dict() #絶対値
    dist = dict()
    for h in range(H):
        grid[h] = dict()
        dist[h] = dict()
        for w in range(W):
            grid[h][w] = 0
            dist[h][w] = set()

    for h in range(H):
        A = [int(a) for a in input().split()]
        for w in range(W):
            grid[h][w] = A[w]
    for h in range(H):
        B = [int(b) for b in input().split()]
        for w in range(W):
            grid[h][w] = abs(grid[h][w] - B[w])
    #print(grid)

    dist[0][0] |= {grid[0][0]}
    for h in range(H):
        for w in range(W):
            for item in dist[h][w]:
                if h < H - 1:
                    n = grid[h+1][w]
                    dist[h+1][w] |= {abs(item + n)}
                    dist[h+1][w] |= {abs(item - n)}
                if w < W - 1:
                    n = grid[h][w+1]
                    dist[h][w+1] |= {abs(item + n)}
                    dist[h][w+1] |= {abs(item - n)}

    #print(dist)
    ans = 1000000
    for item in dist[H-1][W-1]:
        ans = min(ans, item)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    grid = dict() #絶対値
    zero = 12800
    dist = dict()
    for h in range(H):
        grid[h] = dict()
        dist[h] = dict()
        for w in range(W):
            grid[h][w] = 0
            dist[h][w] = 0

    for h in range(H):
        for x, v in enumerate(map(int, input().split())):
            grid[h][x] = v
    for h in range(H):
        for x, v in enumerate(map(int, input().split())):
            grid[h][x] = abs(grid[h][x] - v)

    dist[0][0] |= 2 ** zero >> grid[0][0]
    dist[0][0] |= 2 ** zero << grid[0][0]

    for h in range(H):
        for w in range(W):
            if h < H - 1:
                n = grid[h+1][w]
                dist[h+1][w] |= dist[h][w] >> n
                dist[h+1][w] |= dist[h][w] << n
            if w < W - 1:
                n = grid[h][w+1]
                dist[h][w+1] |= dist[h][w] >> n
                dist[h][w+1] |= dist[h][w] << n
    
    ans = 100000000
    for i in range(zero*2):
        if dist[H-1][W-1] & 1:
            ans = min(ans, abs(i - zero))
        dist[H-1][W-1] >>= 1

    print(ans)

    return 0

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

n = int(input())

ar = [0 for _ in range(n)]

ar = [int(s) for s in input().split()]

res = 1

for i in range(n):
    res = res*ar[i]

if(res > 10**18):
    print(-1)
else:
    print(res)

### FIXED CODE ###

from collections import deque
n = int(input())
d = deque()

ar = [0 for _ in range(n)]

ar = [int(s) for s in input().split()]

ar.sort()
res = 1
flag = 0

if(ar[0] == 0):
    res = 0
else:
    ar = [i for i in ar if i != 1]
    if(len(ar) < 50):
        for i in ar:
            res = res*i
            if(res > 10**18):
                print(-1)
                flag = 1
                break
    else:
        print(-1)
        flag = 1

if(flag == 0):
    print(res)
### BUGGY CODE ###

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)
def comb_mod(n,r):
  r=min(r,n-r)
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  term1=powmod(M-1,N-1)
  inv_M1=invmod(M-1)
  term2=1
  ans_k=M
  for i in range(K+1):
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  print(answer)

### FIXED CODE ###

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

inv_table = [0]+[1]
for i in range(2,K+2):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
elif K==N-1:
  print(powmod(M,N))
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)
### BUGGY CODE ###

xy = input()
XY = xy.split()
X = int(XY[0])
Y = int(XY[1])

a = True
i = 1

if X < Y:
    print(X)
    a = False
elif X > Y:
    while X * i <= X * Y:
        if (X * i) % Y != 0:
            print(X * i)
            a = False
            break
        else:
            i += 1
if a:
    print(-1)

### FIXED CODE ###

xy = input()
XY = xy.split()
X = int(XY[0])
Y = int(XY[1])

a = True
i = 1

if X < Y:
    print(X)
    a = False
elif X > Y and X % Y != 0:
    while X * i <= X * Y:
        if (X * i) % Y != 0:
            print(X * i)
            a = False
            break
        else:
            i += 1
if a:
    print(-1)