Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
while True:
    s,t = input().split()
    a,b = map(int, input().split())
    u = input()

    if u == s:
        a = a - 1
    if u == t:
        b = b - 1

    print(a,b)


Fixed submission:
s,t = input().split()
a,b = map(int, input().split())
u = input()

if u == s:
  a = a - 1
if u == t:
  b = b - 1

print(a,b)
Buggy python submission (verdict: Time Limit Exceeded):

import sys
import math
# from collections import Counter
input = sys.stdin.readline
# import numpy as np

def inp():
    return(int(input()))

def inps():
    return str(input())
    
def inlt():
    return(list(map(int,input().split())))
    
def inlst():
    return(list(map(str,input().split())))
    
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split())) 

x, k, d = inlt()
for i in range(k):
    if x>0: x-=d
    else: x+=d
print(abs(x))    

Fixed submission:

import sys
import math
# from collections import Counter
input = sys.stdin.readline
# import numpy as np

def inp():
    return(int(input()))

def inps():
    return str(input())
    
def inlt():
    return(list(map(int,input().split())))
    
def inlst():
    return(list(map(str,input().split())))
    
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split())) 

def ans(x,k,d):
    if abs(x)<d:
        if k%2: return  d - abs(x)
        else: return abs(x)
    else:
        div = abs(x)//d
        if div>k: return abs(x) - d*k
        else:
            if (k-div)%2: return d - abs(x)%d
            else: return abs(x)%d 

x, k, d = inlt()
print(ans(x, k, d))
Buggy python submission (verdict: Runtime Error):

import sys
import math
input = sys.stdin.readline

    
def inlt():
    return(list(map(int,input().split())))


n, k = inlt()
p = inlt()
p = math.sort(p)
print(sum(p[:k]))




Fixed submission:

import sys
input = sys.stdin.readline

    
def inlt():
    return(list(map(int,input().split())))


n, k = inlt()
p = inlt()
p = sorted(p)
print(sum(p[:k]))
Buggy python submission (verdict: Runtime Error):
r = 0
if 'r' not in s:
  print(0)
else:
  for i in range(len(s)):
    if s[i] == 'r' and i!=len(s)-1:
      for j in range(i+1,len(s)):
        if s[j] != 'r':
          break
      r = j-i
  print(r)
  

Fixed submission:
import re
r = 0
s = input()
if 'R' not in s:
  print(0)
else:
  x = re.findall('R+',s)
  if len(x) == 2:
      print(1)
  else:
      print(len(x[0]))
Buggy python submission (verdict: Runtime Error):
    a,b = input().split(' ')
    if a == b:
      print('Yes')
    else:
      print('No')

Fixed submission:
a,b = input().split(' ')
if a == b:
  print('Yes')
else:
  print('No')
Buggy python submission (verdict: Runtime Error):
a=list(map(int,input().split()))
print(a.find(0)+1)


Fixed submission:
a=list(map(int,input().split()))
print(a.index(0)+1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
if 7 in n:
    print('Yes')
else:
    print('No')

Fixed submission:
n=input()
if '7' in n:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
n=int(input())
if '7' in n:
    print('Yes')
else:
    print('No')

Fixed submission:
n=input()
if '7' in n:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a>=10:
    print(b)
else:
    print(b+100(10-a))

Fixed submission:
a,b=map(int,input().split())
if a>=10:
    print(b)
else:
    print(b+100*(10-a))

Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if n>=10:
    print(b)
else:
    print(b+100(10-a))

Fixed submission:
a,b=map(int,input().split())
if a>=10:
    print(b)
else:
    print(b+100*(10-a))
Buggy python submission (verdict: Runtime Error):
h,a=map(int,input.split())
cnt=0
while True:
    h-=a
    cnt+=1
    if h<=0:
        break
print(cnt)

Fixed submission:
h,a=map(int,input().split())
cnt=0
while True:
    h-=a
    cnt+=1
    if h<=0:
        break
print(cnt)

Buggy python submission (verdict: Runtime Error):
h,a=map(int,input.split())
cnt=0
while h>0:
    h-=a
    cnt+=1
print(cnt)

Fixed submission:
h,a=map(int,input().split())
cnt=0
while True:
    h-=a
    cnt+=1
    if h<=0:
        break
print(cnt)

Buggy python submission (verdict: Runtime Error):
h,a=map(int,input.split())
cnt=0
while h>=0:
    h-=a
    cnt+=1
print(cnt)

Fixed submission:
h,a=map(int,input().split())
cnt=0
while True:
    h-=a
    cnt+=1
    if h<=0:
        break
print(cnt)

Buggy python submission (verdict: Runtime Error):
h,a=map(int,input.split())
cnt=0
while h>=0:
    h-=a
    cnt+=1
print cnt

Fixed submission:
h,a=map(int,input().split())
cnt=0
while True:
    h-=a
    cnt+=1
    if h<=0:
        break
print(cnt)
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())
x=[1,2,3]
x=x.remove(a)
x=x.remove(b)
print(x[0])

Fixed submission:
a=int(input())
b=int(input())
x=[1,2,3]
x.remove(a)
x.remove(b)
print(x[0])

Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())
x=[1,2,3]
x=x.remove(a)
x=x.remove(b)
print(x)

Fixed submission:
a=int(input())
b=int(input())
x=[1,2,3]
x.remove(a)
x.remove(b)
print(x[0])

Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())
x=[1,2,3]
print(x.remove(a,b))

Fixed submission:
a=int(input())
b=int(input())
x=[1,2,3]
x.remove(a)
x.remove(b)
print(x[0])
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())
if a>9 or b>9:
    print(-1)
print(a*b)

Fixed submission:
a,b=(int(x) for x in input().split())
if a>9 or b>9:
    print(-1)
else:
    print(a*b)
Buggy python submission (verdict: Runtime Error):
a=int(input())
if a%2==0:
    print(a/2/a)
else:
    print((a//2+1)a)

Fixed submission:
a=int(input())
if a%2==0:
    print(a/2/a)
else:
    print((a//2+1)/a)
Buggy python submission (verdict: Runtime Error):
a,b,cmap(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-a+b)

Fixed submission:
a,b,c=map(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-(a-b))

Buggy python submission (verdict: Runtime Error):
a,b,cmap(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-a-b)

Fixed submission:
a,b,c=map(int,input().split())
if a-b>=c:
    print(0)
else:
    print(c-(a-b))
Buggy python submission (verdict: Runtime Error):
r=int(input())
print(int(3*r**))

Fixed submission:
r=int(input())
print(int(3*r*r))
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])

Fixed submission:
a,b=map(int,input().split())
s=input()
print(s[:b-1]+s[b-1].lower()+s[b:])

Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower+s[k:])

Fixed submission:
a,b=map(int,input().split())
s=input()
print(s[:b-1]+s[b-1].lower()+s[b:])
Buggy python submission (verdict: Runtime Error):
a,b,t=map(int,input().split())
print(int(((t+0.5)//a*b))

Fixed submission:
a,b,t=map(int,input().split())
x=((t+0.5)//a)
print(int(x*b))
Buggy python submission (verdict: Runtime Error):
n=list(int(input().split()))
if n[0]==n[1]:
    print(n[0]*2)
else:
    print(max(n)*2-1)

Fixed submission:
n=list(map(int,input().split()))
if n[0]==n[1]:
    print(n[0]*2)
else:
    print(max(n)*2-1)

Buggy python submission (verdict: Runtime Error):
n=list(int(input()))
if n[0]==n[1]:
    print(n[0]*2)
else:
    print(max(n)*2-1)

Fixed submission:
n=list(map(int,input().split()))
if n[0]==n[1]:
    print(n[0]*2)
else:
    print(max(n)*2-1)
Buggy python submission (verdict: Runtime Error):
n=input()
result=''
for i in n:
    if i==1:
        result+=9
    else:
        result+=1
print(result)

Fixed submission:
n=input()
result=''
for i in n:
    if i=='1':
        result+='9'
    else:
        result+='1'
print(result)

Buggy python submission (verdict: Runtime Error):
n=input()
result=''
for i in n:
    if i==1:
        result+=9
    else:
        result+=1
    print(result)

Fixed submission:
n=input()
result=''
for i in n:
    if i=='1':
        result+='9'
    else:
        result+='1'
print(result)

Buggy python submission (verdict: Runtime Error):
n=input()
result=''
for i in n:
    if i=='1':
        result+=9
    else:
        result+=1
    print(result)

Fixed submission:
n=input()
result=''
for i in n:
    if i=='1':
        result+='9'
    else:
        result+='1'
print(result)

Buggy python submission (verdict: Runtime Error):
n=input()
result=''
for i in n:
    if i=='1':
        result.append('9')
    else:
        result.append('1')
    print(result)

Fixed submission:
n=input()
result=''
for i in n:
    if i=='1':
        result+='9'
    else:
        result+='1'
print(result)
Buggy python submission (verdict: Runtime Error):
a=list(map(int,input().split()))
b=a.sorted
print(b[1]-b[0]+b[2]-b[1])

Fixed submission:
a=list(map(int,input().split()))
b=sorted(a)
print(b[1]-b[0]+b[2]-b[1])
Buggy python submission (verdict: Runtime Error):
n=int(input())
if n% !=0:
    print(2*n)
else:
    print(n)

Fixed submission:
n=int(input())
if n%2 !=0:
    print(2*n)
else:
    print(n)
Buggy python submission (verdict: Runtime Error):
a=list(input().split())
b=list(input().split())
c=list(input().split())
print(a[0]+b[1]+c[2])

Fixed submission:
a=input()
b=input()
c=input()
print(a[0]+b[1]+c[2])
Buggy python submission (verdict: Runtime Error):
n,a,b=map(int,input().split())
if n*a<b:
    print(n*a)
else:
    print(B)

Fixed submission:
n,a,b=map(int,input().split())
if n*a<b:
    print(n*a)
else:
    print(b)
Buggy python submission (verdict: Runtime Error):
lst=['A','B','C','D','E','F']
a=input()
if lst.index(a[0])>lst.index(a[1]):
    print('>')
elif lst.index(a[0])==lst.index(a[1]):
    print('=')
else:
    print('<')

Fixed submission:
lst=['A','B','C','D','E','F']
a=input()
if lst.index(a[0])>lst.index(a[2]):
    print('>')
elif lst.index(a[0])==lst.index(a[2]):
    print('=')
else:
    print('<')
Buggy python submission (verdict: Runtime Error):
c11,c12,c13=map(int,input().split())
c21,c22,c23=map(int,input().split())
if c11==c23:
    print('YES')
elif c12==c22:
    print('YES')
elif c13==c31:
    print('YES')
else:
    print('NO')

Fixed submission:
a=input()
b=input()
if a[0]==b[2] and a[1]==b[1] and a[2]==b[0]:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
n=input()
if n.count(9)>=1:
    print('Yes')
else:
    print('No')

Fixed submission:
n=input()
if n.count('9')>=1:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
n=input()
if n%10==9 or n>=90:
    print('Yes')
else:
    print('No')

Fixed submission:
n=input()
if n.count('9')>=1:
    print('Yes')
else:
    print('No')

Buggy python submission (verdict: Runtime Error):
n=input()
if n//10==9 or n>=90:
    print('Yes')
else:
    print('No')

Fixed submission:
n=input()
if n.count('9')>=1:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
x,a,c=map(int,input().split())
if abs(x-a)<=abs(x-b):
    print('A')
else:
    print('B')

Fixed submission:
x,a,b=map(int,input().split())
if abs(x-a)<=abs(x-b):
    print('A')
else:
    print('B')

Buggy python submission (verdict: Runtime Error):
import math
x,a,c=map(int,input().split())
if math.abs(x-a)<math.abs(x-b):
    print('A')
else:
    print('B')

Fixed submission:
x,a,b=map(int,input().split())
if abs(x-a)<=abs(x-b):
    print('A')
else:
    print('B')

Buggy python submission (verdict: Runtime Error):
import math
x,a,c=map(int,input().split())
if math.fabs(x-a)<math.fabs(x-b):
    print('A')
else:
    print('B')

Fixed submission:
x,a,b=map(int,input().split())
if abs(x-a)<=abs(x-b):
    print('A')
else:
    print('B')
Buggy python submission (verdict: Runtime Error):
a,b=map(int,input().split())
if a%3==0 or b%3==0: or (a+b)%3==0:
    print ('Possible')
else:
    print('Impossible')

Fixed submission:
a,b=map(int,input().split())
if a%3==0 or b%3==0 or (a+b)%3==0:
    print ('Possible')
else:
    print('Impossible')
Buggy python submission (verdict: Runtime Error):
a,b=(int(x) for x in input().split())
if a=='H':
    if b=='H':
        print("H")
    elif b=='D':
        print("D")
elif a=='D':
    if b=='H':
        print("D")
    elif b=='D':
        print("H")

Fixed submission:
a,b=input().split()
if a=='H':
    if b=='H':
        print("H")
    elif b=='D':
        print("D")
elif a=='D':
    if b=='H':
        print("D")
    elif b=='D':
        print("H")
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
line = list(map(int,input().split()))
a = line[0]
for i in range(len(line)):
    if i == 0:
        pass
    else:
        a = a * line[i]
if a > 10**18:
    print(-1)
else:
    print(a)

Fixed submission:
N = int(input())
line = list(map(int,input().split()))

if line.count(0) > 0:
    a = 0
elif line.count(10**18) > 0:
    a = -1
else:
    a = line[0]
    for i in range(len(line)):
        if i == 0:
            pass
        else:
            a = a * line[i]
            if a > 10**18:
                a = -1
                break

print(a)
Buggy python submission (verdict: Runtime Error):
N = input

if N[-1:] == "2"or"4"or"5"or"7"or"9":
    print("hon")
elif N[-1:] == "0"or"1"or"6"or"8":
    print("pon")
elif N[-1:] == "3":
    print("bon")

Fixed submission:
N = input()
n = N[-1:]

if n == "2" or n == "4" or n == "5" or n == "7" or n == "9":
    print("hon")
elif n == "0" or n == "1" or n == "6" or n == "8":
    print("pon")
elif n == "3":
    print("bon")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
LA = [int(input()) for i in range(n)]
LB = []
LB.extend(LA)
for i in range(n):
    del LB[i]
    print(max(LB))
    LB = []
    LB.extend(LA)

Fixed submission:
n = int(input())
LA = [int(input()) for i in range(n)]
LB = []
LB.extend(LA)
LA.sort()
z = LA[-1]
y = LA[-2]
for i in range(n):
    if LB[i] == z:
        print(y)
    else:
        print(z)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = list(input())
L = []
for i in range(N):
    tmp = S[:i].count("W")+S[i+1:].count("E"); L.append(tmp)
    if tmp == 1: break
print(min(L))

Fixed submission:
N = int(input())
S = input()
 
oE = S.count("E")
Wo = 0

L = []
for i in range(N):
    if i == 0:
        if S[i] == "E":
            oE -= 1
    else:
        if S[i-1] == "W":
            Wo += 1
        if S[i] == "E":
            oE -= 1
    L.append(Wo + oE)
    if Wo + oE == 0:
        break
print(min(L))
Buggy python submission (verdict: Time Limit Exceeded):
N,Y = map(int,input().split())
a,b,c = N+1,N+1,N+1
dama = 0
count = 0

if Y // N == 10000:
    print(N,0,0)
elif Y // N == 5000:
    print(0,N,0)
elif Y // N == 1000:
    print(0,0,N)
else:
    stop = False
    for i in range(a):
        if stop:
            break
        b -= i
        for j in range(b):
            if stop:
                break
            c -= i+j
            for k in range(c):
                if i+j+k != N:
                    pass
                else:
                    dama = 10000*i + 5000*j + 1000*k
                    if dama == Y:
                        print(i,j,k)
                        count += 1
                        stop = True
                        break
            c = N+1
        b = N+1
    if count == 0:
        print(-1,-1,-1)

Fixed submission:
N,Y = map(int,input().split())
a,b,c = N+1,N+1,N+1
dama = 0
count = 0

if Y // N == 10000:
    print(N,0,0)
elif Y // N == 5000:
    print(0,N,0)
elif Y // N == 1000:
    print(0,0,N)
else:
    stop = False
    for i in range(a):
        if stop:
            break
        b -= i
        for j in range(b):
            if stop:
                break
            c -= i+j
            if i+j+c != N:
                pass
            else:
                dama = 10000*i + 5000*j + 1000*c
                if dama == Y:
                    print(i,j,c)
                    count += 1
                    stop = True
                    break
            c = N
        b = N+1
    if count == 0:
        print(-1,-1,-1)

Buggy python submission (verdict: Time Limit Exceeded):
N,Y = map(int,input().split())
a,b,c = N+1,N+1,N+1
dama = 0
count = 0

if Y // N == 10000:
    print(N,0,0)
elif Y // N == 5000:
    print(0,N,0)
elif Y // N == 1000:
    print(0,0,N)
else:
    stop = False
    for i in range(a):
        if stop:
            break
        b -= i
        for j in range(b):
            if stop:
                break
            c -= i+j
            for k in range(c):
                if i+j+k == N:
                    dama = 10000*i + 5000*j + 1000*k
                    if dama == Y:
                        print(i,j,k)
                        count += 1
                        stop = True
                        break
            c = N+1
        b = N+1
    if count == 0:
        print(-1,-1,-1)

Fixed submission:
N,Y = map(int,input().split())
a,b,c = N+1,N+1,N+1
dama = 0
count = 0

if Y // N == 10000:
    print(N,0,0)
elif Y // N == 5000:
    print(0,N,0)
elif Y // N == 1000:
    print(0,0,N)
else:
    stop = False
    for i in range(a):
        if stop:
            break
        b -= i
        for j in range(b):
            if stop:
                break
            c -= i+j
            if i+j+c != N:
                pass
            else:
                dama = 10000*i + 5000*j + 1000*c
                if dama == Y:
                    print(i,j,c)
                    count += 1
                    stop = True
                    break
            c = N
        b = N+1
    if count == 0:
        print(-1,-1,-1)
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, m, k = geta(int)
    ca = np.array([0] + list(geta(int))).cumsum()
    cb = np.array([0] + list(geta(int))).cumsum()

    ans = 0
    for i in range(n+1):
        if ca[i] > k:
            break
        j = np.searchsorted(cb, k-ca[i], side="right") - 1
        if ans < i + j:
            ans = i + j

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import numpy as np
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, m, k = geta(int)
    a = np.array([0] + list(geta(int)))
    b = np.array([0] + list(geta(int)))

    ca = np.cumsum(a)
    cb = np.cumsum(b)

    ans = 0
    for i, ai in enumerate(ca):
        if k < ai:
            break

        j = np.searchsorted(cb, k-ai, side="right") - 1

        if ans < i + j:
            ans = i + j

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n = gete(int)

    ans = 0
    for i in range(1, n+1):
        m = n//i
        ans += i * m * (m+1) // 2

    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n = gete(int)

    ans = 0
    for i in range(1, n+1):
        m = n//i
        ans += i * m * (m+1) // 2

    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, k = geta(int)
    a = tuple(geta(int))

    def update(b):
        r = [0] * n
        for i, bi in enumerate(b):
            i1 = max(0, i - bi)
            i2 = min(n - 1, i + bi)
            r[i1] += 1

            if i2 < n - 1:
                r[i2 + 1] -= 1

        for i in range(1, n):
            r[i] += r[i - 1]

        return r

    for i in range(k):
        a = update(a)

    print(*a, sep=" ")


if __name__ == "__main__":
    main()

Fixed submission:
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    n, k = geta(int)
    a = tuple(geta(int))

    def update(b):
        r = [0] * n
        for i, bi in enumerate(b):
            i1 = max(0, i - bi)
            i2 = min(n - 1, i + bi)
            r[i1] += 1

            if i2 < n - 1:
                r[i2 + 1] -= 1

        updated = (not r[0] == b[0])
        for i in range(1, n):
            r[i] += r[i - 1]
            if r[i] != b[i]:
                updated = True

        return r, updated

    for i in range(k):
        a, updated = update(a)
        if not updated:
            break

    print(*a, sep=" ")


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
# import sys
# sys.setrecursionlimit
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)


Fixed submission:
import sys
sys.setrecursionlimit(10**5)
# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))


def egcd(a: int, b: int):
    """
    A solution of ax+by=gcd(a,b). Returns
    (gcd(a,b), (x, y)).
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(a: int, m: int):
    """
    Returns a^{-1} modulo m.
    """
    g, x, y = egcd(a, m)
    if g > 1:
        raise Exception('{}^(-1) mod {} does not exist.'.format(a, m))
    else:
        return x % m


def modpow(a: int, n: int, m: int):
    """
    Returns a^n mod m. (-inf < n < inf)
    """
    if a in [-1, 0, 1]:
        if a == -1:
            return 1 if n & 1 == 0 else m - 1
        else:
            return a

    x, k = (a % m, n) if n >= 0 else (modinv(a, m), -n)

    ret = 1
    while k > 0:
        if k & 1 == 1:
            ret = ret * x % m
        x *= x
        k = k >> 1

    return ret


mod = 998244353

N, M, K = geta(int)

if M == 1:
    print(0 if K < N - 1 else 1)
    exit()

a = M * modpow(M - 1, N - 1, mod) % mod
ans, k = a, 1
mi = modinv(M - 1, mod)

for k in range(1, K + 1):
    a = a * (N - k) * mi * modinv(k, mod) % mod
    ans = (ans + a) % mod

print(ans)