Harryxun/stf_run huggingface dataset:
N, M, K = [int(i) for i in input().split(" ")]

friend_list = []
block_list = []
union = [None for i in range(N)]
next = 0

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1

    friend_list.append((a, b))

    if union[a] is union[b] is None:
        union[a] = next
        union[b] = next
        next += 1

    elif union[a] is None:
        union[a] = union[b]
    elif union[b] is None:
        union[b] = union[a]

    elif union[a] > union[b]:
        umax = union[a]
        umin = union[b]

        for j in range(M):
            if union[j] == umax:
                union[j] = umin

    elif union[b] > union[a]:
        umax = union[b]
        umin = union[a]

        for j in range(M):
            if union[j] == umax:
                union[j] = umin



for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    block_list.append((a, b))

result = []
for i in range(N):
    ret = 0
    for j in range(N):
        if i == j:
            continue

        if union[i] != union[j]:
            continue
        if (i, j) in block_list:
            continue
        if (j, i) in block_list:
            continue
        if (i, j) in friend_list:
            continue
        if (j, i) in friend_list:
            continue

        ret += 1
    result.append(ret)

#print(result)
print(" ".join([str(i) for i in result]))

### FIXED CODE ###

from collections import defaultdict
import sys
import time

sys.setrecursionlimit(2000)
N, M, K = [int(i) for i in input().split(" ")]

t = time.time()
class UnionNode():
    def __init__(self, number):
        self.number = number
        self.volume = 1
        self.master = None

    @property
    def root(self):
        if self.master:
            self.master = self.master.root
            return self.master
        else:
            return self

    def unite(self, target):
        seroot = self.root
        taroot = target.root
        if seroot.number == taroot.number:
            pass
        else:
            #print(f"unite {target.rootnum}({target.root.volume}), {self.rootnum}({self.root.volume})")
            if seroot.number < taroot.number:
                seroot.volume += taroot.volume
                taroot.master = seroot
            else:
                taroot.volume += seroot.volume
                seroot.master = taroot

nodes = [UnionNode(i) for i in range(N)]

outlist = defaultdict(lambda :[])

for i in range(M):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    nodes[a].unite(nodes[b])
    outlist[a].append(b)
    outlist[b].append(a)

for i in range(K):
    s = input()
    a, b = s.split(" ")
    a = int(a) - 1
    b = int(b) - 1
    outlist[a].append(b)
    outlist[b].append(a)

result = []
for i in range(N):
    rootnode = nodes[i].root
    ret = rootnode.volume - 1
    for out in outlist[i]:
        if nodes[out].root.number == rootnode.number:
            ret -=1
    result.append(ret)

#for i in range(100):
#    print(result[i])

print(" ".join([str(i) for i in result]))

#print(time.time() - t)
import math
x = int(input())
ans = (int(math.sqrt(X)))**2
for i in range(2,int(math.sqrt(x))+2):
  for j in range(1,10):
    if i ** j <= x and i**j > ans:
      ans = i**j

print(ans)




### FIXED CODE ###

import math
X = int(input())
n = (int(math.sqrt(X)))**2
for b in range(2, int(math.sqrt(X))+2):
    for p in range(1, 10):
        if (b**p > n) and (b**p <= X):
            n = b**p
print(n)
x=raw_input()
y=raw_input()
z=raw_input()
w=(int(z+0.5/x)*y)
print(w)

### FIXED CODE ###

s=list(map(int,input().split()))
a=s[2]%s[0]
c=s[2]-a
d=c/s[0]
b=d*s[1]
print(int(b))
N, K = map(int, input().split())
inputs = [int(i) for i in input().split()]

dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    if i == 1:
        dp[i] = abs(inputs[i] - inputs[i-1])
    else:
        tmp = 10 ** 9
        start = max(0, i-K)
        dp[i] = min([dp[start] + abs(inputs[i-(j+1)] - inputs[i]) for j in range(start, i-1)])

print(dp[-1])



### FIXED CODE ###

import numpy as np


N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()

print(dp[-1])
h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [-1 for _ in range(h+max(skills) + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==-1:
    continue
  for damage,mp in skill:
    if dp[i+mp] < dp[i] + damage:
      dp[i+mp] = dp[i]+damage
print(min(dp[h:]))

### FIXED CODE ###

h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min(filter(lambda x :x>0,dp[h:]))
print(ans)
#print(dp)
n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

def solve(i, m):
if m == 0:
return True
if i >= n and m > sum(A)
return False
res = solve(i + 1, m) or solve(i + 1, m - A[i])
return res

for m in M
   if res = solve(0,m):
      print 'yes'
   else:
      print 'no'

### FIXED CODE ###

n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

def solve(i, m):
   if m == 0:
     return True
   if i >= n or m > sum(A):
     return False
   res = solve(i + 1, m) or solve(i + 1, m - A[i])
   return res

for m in M:
  if solve(0,m):
     print "yes"
  else:
     print "no"
n = int(input())
card=[i + '' + str(j) for i in ['S','H','C','D'] for j in range(1,14)]

for i in range(n):
  card.remove(input())
  
for i in card:
  print(card)


### FIXED CODE ###

n = int(input())
card =[i+" "+str(j) for i in ["S","H","C","D"] for j in range(1,14)]
for i in range(n):
    card.remove(input())
for i in card:
    print(i)
n=list(input())

if (n[3]==n[4] and n[5]==n[6]):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n=list(input())

if n[2]==n[3] and n[4]==n[5]:
    print("Yes")
else:
    print("No")
_, K = map(int, input().split())
a = list(map(int, input().split()))
s = [sum([b > c for c in a]) for b in a]
r = [sum([b > c for c in a[i:]]) for i, b in enumerate(a)]
b = (sum(r) + sum(s)*(K-1)/2)*K + sum(r)
print(int(b%(1e9+7)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 24 21:04:16 2019

@author: Toroi0610
"""

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

M, D = map(int, input().split())
day = [str(d) for d in range(1, D+1)]
cnt = 0
for m in range(1, M+1):
    s = make_divisors(m)
    length = len(s)
    if length == 2:
        continue
    if length%2 == 0:
        for l, r in zip(s[:int(length/2)], s[int(length/2):][::-1]):
            if (l > 10) or (r > 10) or (l==1):
                continue
            else:
                if str(l)+str(r) in day:
                    cnt += 1
                if str(r)+str(l) in day:
                    cnt += 1
    else:
        for l, r in zip(s[:int(length/2)+1], s[int(length/2):][::-1]):
            if (l > 10) or (r > 10) or (l==1):
                continue
            else:
                if str(l)+str(r) in day:
                    cnt += 1
                if l != r:
                    if str(r)+str(l) in day:
                        cnt += 1
print(cnt)
N,X,T = map(int, input().split())
a = N/X
if N%X != 0:
  a += 1
return a * T


### FIXED CODE ###

N,X,T = map(int, input().split())
a = int(N/X)
if N%X != 0:
  a += 1
print(int(a * T))
from functools import lru_cache
import sys 
sys.setrecursionlimit(2147483647)

N = int(input())
A = []
for i in range(0,N):
    A.append(list(map(int,input().split())))


#@lru_cache(None)
def dfs(d,pre):
    if (d,pre) in dic: return dic[(d,pre)]
    if d>=N-1: return 0
    ma = 0 
    for idx,a in enumerate(A[d]):
        if idx != pre:
            res = dfs(d + 1,idx) + a 
            ma = max(res,ma)
    dic[(d,pre)] = ma
    return ma
dic = {}
res = dfs(-1,-1)
print(res)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    if i - 2>=0:
        dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]))
    else:
        dp[i] =dp[i-1] + abs(A[i] - A[i-1])

print(dp[len(A)-1])
#include <bits/stdc++.h>
using namespace std;
int main() 
{
    char a[10010];
    bool c, f;
    fgets(a,10010,stdin);
    for(int i=1;i<=strlen(a);i++) 
    {
        if(a[i]=='C') 
        {
            for(int j=i+1;j<=strlen(a)-i;j++)
            {
                if(a[j]=='F')
                {
                    printf("Yes\n");
                    return 0;
                }
            }
        }
    }
    printf("No\n");
    return 0;
}

### FIXED CODE ###

s=input();pd=0
for i in range(0,len(s)):
    if s[i]=='C':
        pd=1
    if s[i]=='F'and pd==1:
        print('Yes')
        pd=2
        break
if pd!=2:
    print('No')
num = list(map(int,input().split()))

print(num[0] + " " + num[1])


### FIXED CODE ###

num = list(map(int,input().split()))

print("%d %d" % (num[0]*num[1],(num[0]+num[1])*2))
a = input()
b = input()
if a % 500 <= b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a = int(input())
b = int(input())
temp = a % 500
if temp <= b:
  print("Yes")
else:
  print("No")
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
m = nsn(h)

dist = [[inf] * (h * w) for _ in range(h * w)]
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
for i in range(h):
    for j in range(w):
        for k in range(4):
            ni, nj = i + dy[k], j + dx[k]
            if ni >= 0 and ni < h and nj >= 0 and nj < w and m[ni][nj] != '#' and m[i][j] != '#':
                dist[i * h + j][ni * h + nj] = 1
        dist[i * h + j][i * h + j] = 0

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

floyd_warshall(h * w, dist)

ans = 0
for i in range(h * w):
    for j in range(h * w):
        if dist[i][j] != inf:
            ans = max(ans, dist[i][j])

print(ans)

### FIXED CODE ###

import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

from collections import deque

h, w = na()
s = [ns() for i in range(h)]
maze = [[s[i][j] for j in range(w)] for i in range(h)]
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs(sx, sy):
    q = deque()
    inf = 1 << 60
    d = [[inf for i in range(w)] for i in range(h)]
    d[sy][sx] = 0
    q.append((sx, sy))
    mx = 0
    while len(q):
        p = q.popleft()
        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and maze[ny][nx] != '#' and d[ny][nx] == inf:
                q.append((nx, ny))
                update = d[p[1]][p[0]] + 1
                d[ny][nx] = update
                mx = max(mx, update)
    return mx

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            ans = max(ans, bfs(j, i))

print(ans)
K,N=map(int,input().split())
A=list(map(int,input().split()))
l=0
for i in range(N-2):
    if (A[i+2]-A[i+1])>=(A[i+1]-A[i]):
        l=A[i+2]-A[i+1]
if (20-A[N-1]+A[0])>=l:
print(K-l)

### FIXED CODE ###

K,N=map(int,input().split())
A=list(map(int,input().split()))
d=[]
for i in range(N-1):
    d.append(A[i+1]-A[i])
d.append(K-A[N-1]+A[0])
print(K-max(d))
# coding: utf-8
n=int(input().split())
a=0
for i in range(1,n+1):
    a+=i
print(a)

### FIXED CODE ###

# coding: utf-8
n=int(input())
a=0
for i in range(1,n+1):
    a+=i
print(a)
a, b, c, d = map(int, input().split())

print(min(a, b) + min(c, d))


### FIXED CODE ###

a= int(input())
b= int(input())
c= int(input())
d= int(input())

print(min(a, b)+min(c,d))
while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):
        if i%2 = 1:
            sym1 = "#"
            sym2 = "."
        else:
            sym1 = "."
            sym2 = "#"

        for j in range(w):
            if j%2 == 1:
                print(sym1,end="")
            else:
                print(sym2,end="")
        print("")
    
    print("")

### FIXED CODE ###

while True:
    h,w = map(int,input().split())
    if h == 0 and w == 0:
        break
    for i in range(h):
        if i%2 == 1:
            sym1 = "#"
            sym2 = "."
        else:
            sym1 = "."
            sym2 = "#"

        for j in range(w):
            if j%2 == 1:
                print(sym1,end="")
            else:
                print(sym2,end="")
        print("")
    
    print("")
n = int(input())

a = list(map(int,input().split())))
if n ==len(set(a)):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if len(set(a)) == n:
    print("YES")
else:
    print("NO")
tb, x = input().split()
ta = tb/x
print(ta)

### FIXED CODE ###

tb, x = input().split()
ta = int(tb)/int(x)
print(ta)
a,b = map(int,input().split)
print((a-1)*(b-1))

### FIXED CODE ###

a,b = map(int,input().split())
print((a-1)*(b-1))
# coding: UTF-8


N, _ = input().split()
dislike_nums = set(map(int, input().split()))

nums = set(range(10))
nums -= dislike_nums

for i in range(len(N)):
    Ni = int(N[i])
    larger_num = [n for n in nums if n >= Ni]
    print(min(larger_num), end="")

print()



### FIXED CODE ###

# coding: UTF-8


N, _ = input().split()
N = int(N)

dislike_nums = input().split()

def contains_dislike_number(num):
    for n in dislike_nums:
        if n in str(i):
            return True
    return False

for i in range(N, 10*N+1):
    if not contains_dislike_number(i):
        print(i)
        break
N = int(input())
lst = list(map(int, input().split()))
boolean = False
updated_lst = []
min = min(lst)
min_num = 0
for i in lst:
  num = i % min
  if (i != min):
    updated_lst.append(num)
  else:
    updated_lst.append(min)
    min_num += 1
  if (num % 2 == 1):
    buulean = True

sum = sum(updated_lst)

if (sum == min*min_num):
  print(min)
else:
  if (boolean):
    print(1)
  else:
    print(min(updated_lst))  

### FIXED CODE ###

import fractions
N = int(input())
lst = list(map(int, input().split()))
ans = lst[0]
for i in range(1, N):
    ans = fractions.gcd(ans, lst[i])
print(ans)
A, B = int(input())
if 1<=A & A<=9 | 1<=B & B<=9:
    if 1<=A*B & A*B<=81:
        print (A*B)
    else:
        print (-1)



### FIXED CODE ###

A, B = map(int, input().split())
if 1 <= A <= 9 and 1 <= B <= 9:
    print(A*B)
else:
     print (-1)
n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n)
while n > 26:
    r = n % 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
if l >= 2:
    for i in range(1, l):
        rev[i] += 1
name = []

for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i] - 1]
    name.append(d)
dogname = ''.join(name)
print(dogname)

### FIXED CODE ###

n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n) - 1
while n > 25:
    r = n % 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
name = []
for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i]]
    name.append(d)
dogname = ''.join(name)
print(dogname)
# coding: utf-8
# Here your code !

from numpy import array, dot

def func():
    try:
        (n,m) = tuple( [ int(num) for num in input().rstrip().split(" ") ] )
        matrix = array( [ [int(num) for num in input().rstrip().split(" ")] for i in range(n) ] )
        vector = array( [ int( input().rstrip() ) for i in range(m) ] )
    except:
        return inputError()

    result = dot(matrix,vector)
    for num in result:
        print(num)
    
def inputError():
    print("input error")
    return -1

func()

### FIXED CODE ###

# coding: utf-8
# Here your code !

def func():
    try:
        (n,m) = tuple( [ int(num) for num in input().rstrip().split(" ") ] )
        matrix = [ [int(num) for num in input().rstrip().split(" ")] for i in range(n) ]
        vector = [ int( input().rstrip() ) for i in range(m) ]
    except:
        return inputError()

    result = [ sum( [ matrix[j][i]*vector[i] for i in range(m) ] ) for j in range(n)  ] #????????¨??????????????????

    for num in result:
        print(num)
    
def inputError():
    print("input error")
    return -1

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

A = sorted(A)
ans = a[2] - a[0]
print(ans)

### FIXED CODE ###

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

A = sorted(A)
ans = A[2] - A[0]
print(ans)
a =  int(input())
a = list(map(int, input().split()))
a.sort()

d_num = a

div = []
a_set = list(set(a))
flag = false
if len(a_set) == 1:
    print(0)
else:
    for i in range(len(a_set)):
        flag = false
        # for j in range(len(div)):
        #     if(a_set[i]%div[j] == 0):
        #         d_num -= 1
        #         flag = true
        #         break
        if flag == false:
            div.append(a_set[i])
    print(1)


### FIXED CODE ###

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

ndiv_sum = 0
max_num = A[-1]
no_div = [True] * (max_num+1)
for i in range(len(A)-1):
    if no_div[A[i]]:
        for j in range(A[i], max_num+1, A[i]):
            no_div[j] = False
        if A[i]!=A[i+1]:
            ndiv_sum += 1
if no_div[A[-1]]:
    ndiv_sum += 1
print(ndiv_sum)
s=input()
if len(s)==2;print(s)
else:print(s[::-1])

### FIXED CODE ###

s=input()
if len(s)==2:print(s)
else:print(s[::-1])
W,H,x,y=map(int,input().split())

print(H*W/2,end=" ")
if x==W/2 and y==H/w:
	print(1)
else:
	print(0)

### FIXED CODE ###

W,H,x,y=map(int,input().split())

print(H*W/2,end=" ")
if x==W/2 and y==H/2:
	print(1)
else:
	print(0)
import math
N,M = map(int,input().split())
a = list(map(int,input().split()))

def count_2(x):
    count = 0
    while x%2 == 0:
        count += 1
        x /= 2
    return count

flag = True

for i in range(N-1):
    if count_2(a[i]) != count_2(a[i+1]):
        flag = False
        break
    
if not flag:
    print(0)
    exit()

lcm=1
for i in range(N):
    lcm = lcm*a[i]//math.gcd(a[i],lcm)

ans=0
if lcm//2<M:
    ans=(M-lcm//2)//lcm+1

print(ans)

### FIXED CODE ###

from fractions import gcd
N,M = map(int,input().split())
a = list(map(int,input().split()))

def count_2(x):
    count = 0
    while x%2 == 0:
        count += 1
        x /= 2
    return count

flag = True

for i in range(N-1):
    if count_2(a[i]) != count_2(a[i+1]):
        flag = False
        break
    
if not flag:
    print(0)
    exit()

lcm=1
for i in range(N):
    lcm = lcm*a[i]//gcd(a[i],lcm)

ans=0
if lcm//2<=M:
    ans=(M-lcm//2)//lcm+1

print(ans)
from collections import deque
S = input()
N = len(S)
DS = deque(S)    
S1 = deque(S[0:int((N-1)/2)])
S2 = deque(S[int((N+3)/2)-1:N])

s1 = S1
s2 = S2
while len(s1) >= 2:
    if s1.popleft() != s2.pop():
        ans = "No"
        break
    if len(s1) == 1 or len(s1) == 0:
        ans = "preYes"

S1 = deque(S[0:int((N-1)/2)])
S2 = deque(S[int((N+3)/2)-1:N])
if ans == "preYes":
    t1 = S1
    t2 = S2
    while len(t1) >= 2:
        if t1.pop() != t1.popleft():
            ans = "No"
            break
        if len(t1) == 1 or len(t1) == 0:
            ans = "Yes"
print(ans)

### FIXED CODE ###

from collections import deque
S = input()
N = len(S) 
s1 = deque(S[0:int((N-1)/2)])
s2 = deque(S[int((N+3)/2)-1:N])
t1 = deque(S[0:int((N-1)/2)])
t2 = deque(S[int((N+3)/2)-1:N])
ans = "None"
if len(S) == 3 and S[0] == S[2]:
    ans = "Yes"
while len(s1) >= 2:
    if s1.popleft() != s2.pop():
        ans = "No"
        break
    if len(s1) == 1 or len(s1) == 0:
        ans = "preYes"
        break

if ans == "preYes":
    while len(t1) >= 2:
        if t1.pop() != t1.popleft():
            ans = "No"
            break
        if len(t1) == 1 or len(t1) == 0:
            ans = "Yes"
            break
print(ans)
S=input()
print(min(abs(753-int(S[i,i+3])) for i in range(len(S)-2)))

### FIXED CODE ###

S=input()
print(min(abs(753-int(S[i:i+3])) for i in range(len(S)-2)))
from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def binom(n, k, q, F, I):
	return (F[n]*((I[k]*I[n-k])%q))%q

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	ans = 0
	for i in range(n-k, n+1):
		ans += (binom(n-1, i-1, MOD, F, I)*m*pow(m-1, i-1, MOD))%MOD
	print(ans % MOD)

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def binom_tables(n, q):
	fact = [1 for _ in range(n + 1)]
	inv = [1 for _ in range(n + 1)]
	for i in range(1, n+1):
		fact[i] = (fact[i-1] * i) % q
		inv[i] = pow(fact[i], q-2, q)
	return fact, inv

def binom(n, k, q, F, I):
	return (F[n]*((I[k]*I[n-k])%q))%q

def main():
	MOD = 998244353
	n, m, k = rli()
	F, I = binom_tables(n, MOD)
	ans = 0
	for i in range(n-k, n+1):
		ans += (binom(n-1, i-1, MOD, F, I)*m*pow(m-1, i-1, MOD))%MOD
	print(ans % MOD)

if __name__ == "__main__":
	main()