Harryxun/stf_run huggingface dataset:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
flag=True
count=0
for i in range(h):
  if flag==False:
    break
  for j in range(w):
    if s[i][j]=="#":
      if i>0 and s[i-1][j]!="#":
        flag=False
      elif i> and s[i-1][j]=="#":
        flag=True
        break
        
      if i<(h-1) and s[i+1][j]!="#":
        flag=False
      elif i<(h-1) and s[i+1][j]=="#":
        flag=True
        break
        
      if j>0 and s[i][j-1]!="#":
        flag=False
      elif j>0 and s[i][j-1]=="#":
        flag=True
        break
        
      if j<(w-1) and s[i][j+1]!="#":
        flag=False
      elif j<(w-1) and s[i][j+1]=="#":
        flag=True
        break
    else:
      count+=1
        
if h==1 and w==1:
  if s[0][0]=="#":
    flag=False
    
if count==(h*w):
  flag=True
  
if flag:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
flag=True
count=0
for i in range(h):
  if flag==False:
    break
  for j in range(w):
    if flag==False:
      break
    flag2=False
    if s[i][j]=="#":
      if i>0 and s[i-1][j]!="#":
        flag=False
      elif i>0 and s[i-1][j]=="#":
        flag2=True
        
      if i<(h-1) and s[i+1][j]!="#":
        flag=False
      elif i<(h-1) and s[i+1][j]=="#":
        flag2=True
        
      if j>0 and s[i][j-1]!="#":
        flag=False
      elif j>0 and s[i][j-1]=="#":
        flag2=True
      
      if j<(w-1) and s[i][j+1]!="#":
        flag=False
      elif j<(w-1) and s[i][j+1]=="#":
        flag2=True
      if flag2:
        flag=True
    else:
      count+=1
        
if h==1 and w==1:
  if s[0][0]=="#":
    flag=False
    
if count==(h*w):
  flag=True
  
if flag:
  print("Yes")
else:
  print("No")
N = int(input())
A = [int(i) for i in input().split()]
f = 0
A.sort()
for i in range(len(A)):
    # if A.count(i) > 1:
    if A[i] == A[i+1]:
        f = 1
        break
        
if f > 0:
    print("NO")
else:
 print("YES")
    


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
f = 0
A.sort()
for i in range(len(A)):
    if i != len(A)-1:
        if A[i] == A[i+1]:
            f = 1
            break
        
if f > 0:
    print("NO")
else:
    print("YES")
a,b,c,d,e,f=map(int,input().split())
a*=100
b*=100
x=set()
for i in range(f//a+1):
    for j in range(f//b+1):
        if 0<(a*i+b*j)<=f:
            x.add(a*i+b*j)
y=set()
for i in range(f//c+1):
    for j in range(f//d+1):
        if 0<(c*i+d*j)<=f:
            y.add(c*i+d*j)

ans=[]
noudoma=e/100
for n in x:
    for m in y:
        if n==0:
            continue
        if m/n<=noudoma and (n+m)<=f:
            ans.append([n+m,m,m/(n+m)])

ans.sort(key=lambda x:x[2], reverse=True)


print(ans[0][0],ans[0][1])


### FIXED CODE ###

a,b,c,d,e,f=map(int,input().split())
a*=100
b*=100
x=set()
for i in range(0,f+1,a):
    for j in range(0,f+1,b):
        if 0<(i+j)<=f:
            x.add(i+j)
y=set()
for i in range(0,f+1,c):
    for j in range(0,f+1,d):
        if 0<(i+j)<=f:
            y.add(i+j)

ans=[]
for n in x:
    for m in y:
        if n+m>f:
            continue
        if n*e<m*100:
            continue
        ans.append([n+m,m,m/n])
if not ans:
    print(a,0)
    exit()
ans.sort(key=lambda x:x[2], reverse=True)

print(ans[0][0],ans[0][1])
N, K = map(int, input().split())
P = list(map(int, input().split())).sort()
print(sum(P[:K]))


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P.sort()
ans = 0
for p in P[:K]:
    ans += p
print(ans)
n, m =int(input())
print(n-1 * m-1)

### FIXED CODE ###

n, m = map(int, input().split())
print((n-1)*(m-1))
n, a, b, c = list(map(int, input().split()))
ss = []
for i in range(n):
    ss.append(input())
ans = []
num_dic = {"A": a,"B":b, "C": c}

for i in range(n):
    s = ss[i]
    if num_dic[s[0]] == 0 and num_dic[s[1]] == 0:
        print("No")
        exit()
    elif num_dic[s[0]] > num_dic[s[1]]:
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
        ans.append(s[0])
    elif num_dic[s[0]] > num_dic[s[1]]:
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
        ans.append(s[1])
    elif i == n -1:
        ans.append(s[0])
    elif s[0] in S[i+1]:
        num_dic[s[0]] += 1
        num_dic[s[1]] -= 1
        ans.append(s[0])
    else:
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
        ans.append(s[1])
for a in ans:
    print(a)


### FIXED CODE ###

n, a, b, c = list(map(int, input().split()))
ss = []
for i in range(n):
    ss.append(input())
ans = []
num_dic = {"A": a,"B": b, "C": c}

for i in range(n):
    s = ss[i]
    if num_dic[s[0]] == 0 and num_dic[s[1]] == 0:
        print("No")
        exit()
    elif num_dic[s[0]] > num_dic[s[1]]:
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
        ans.append(s[1])
    elif num_dic[s[0]] < num_dic[s[1]]:
        num_dic[s[0]] += 1
        num_dic[s[1]] -= 1
        ans.append(s[0])
    elif i == n -1:
        ans.append(s[0])
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
    elif s[0] in ss[i+1]:
        num_dic[s[0]] += 1
        num_dic[s[1]] -= 1
        ans.append(s[0])
    else:
        num_dic[s[0]] -= 1
        num_dic[s[1]] += 1
        ans.append(s[1])
print("Yes")
for a in ans:
    print(a)
def main2():
    x, y = map(int, input().split())

    delta = abs(abs(x) - abs(y))

    c1 = delta + 0 + 0
    c2 = delta + 0 + 1
    c3 = delta + 1 + 0
    c4 = delta + 1 + 1

    print(min(c1, c2, c3, c4))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    x, y = map(int, input().split())

    if x == y:
        print(0)

    elif abs(x) == abs(y):
        print(1)

    elif x < y:
        if x >= 0 and y >= 0:
            print(y - x)

        elif x >= 0 and y <= 0:
            pass

        elif x <= 0 and y >= 0:
            if y == 0:
                print(abs(x))
            else:
                if abs(y) > abs(x):
                    print(abs(y) - abs(x) + 1)
                else:
                    print(abs(x) - abs(y) + 1)

        elif x <= 0 and y <= 0:
            print(abs(x) - abs(y))

    elif x > y:
        if x <= 0 and y <= 0:
            c1 = abs(y) - x + 1
            c2 = abs(y) - abs(x) + 2
            print(min(c1, c2))

        elif x <= 0 and y >= 0:
            pass

        elif x >= 0 and y <= 0:
            print(max(abs(x), abs(y)) - min(abs(x), abs(y)) + 1)
            
        elif x >= 0 and y >= 0:
            print(x - y + 2)

if __name__ == "__main__":
    main()
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    
    if A[i] % A[j]==0:
      if i==j:
        pass
      else:
        T=False
        break
        
  if T==True:
    sucl.append(i)
print(len(sucl))
    

### FIXED CODE ###

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


for i in range(1,6):
  if list1[i-1] != i:
    print(i)
N = int(input())
info = []
for i in range(N):
    x,y,h = map(int,input().split())
    info.append([x,y,h])
for i in range(101):
    for j in range(101):
        H_0 = info[0][2] + abs(info[0][0] - i) + abs(info[0][1] - j)
        for k in range(1,N):
            if info[k][2] == 0:
                continue
            H = info[k][2] + abs(info[k][0] - i) + abs(info[k][1] - j)
            if H_0 != H:
                break
            elif k == N-1:
                ans = [i,j,H_0]
print(" ".join([str(e) for e in ans]))

### FIXED CODE ###

N = int(input())
info = []
for i in range(N):
    x,y,h = map(int,input().split())
    if h == 0:
        N -= 1
        continue
    info.append([x,y,h])
for i in range(101):
    for j in range(101):
        H_0 = info[0][2] + abs(info[0][0] - i) + abs(info[0][1] - j)
        for k in range(1,N):
            H = info[k][2] + abs(info[k][0] - i) + abs(info[k][1] - j)
            if H_0 != H:
                break
            elif k == N-1:
                print(i,j,H_0)
                exit()
print(info[0][0],info[0][1],info[0][2])
N = int(input())
A = list(map(int, input().split()))
count = 0

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) = 0:
            continue
        else:
            count += 1
            break

print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)
# coding:utf-8
s=input()
k=int(input())
list=list(s)
ans=1
for i in range(min(k,list.len())):
    if not list[i] == 1:
        ans=list[i]
        break
print(ans)


### FIXED CODE ###

# coding:utf-8
s=input()
k=int(input())
lists=list(s)
ans=1
for i in range(min(k,len(lists))):
    if not lists[i] == "1":
        ans=lists[i]
        break
print(ans)
n = int(input())
ans = 0
for i in range(n):
    x, u = input().split()
    s = float(x)
    if u = "JPY":
        ans += s
    else:
        ans += (s * 380000.0)
print(s)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(n):
    x, u = input().split()
    s = float(x)
    if u == "JPY":
        ans += s
    else:
        ans += (s * 380000.0)
print(ans)
A,B = map(int, int().split())
C = A + B
if (C >= 10):
    print("error")
else:
    print(C)


### FIXED CODE ###

A,B = map(int, input().split())
C = A + B
if(C >= 10):
    print("error")
else:
    print(C)
N = int(input())
S = list(input())
K = int(input())
print(key)
for i in range(N):
    if S[i] != key:
        S[i] = "*"
print("".join(S))

### FIXED CODE ###

N = int(input())
S = list(input())
K = int(input())
key = S[K-1]
for i in range(N):
    if S[i] != key:
        S[i] = "*"
print("".join(S))
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
dif = [0] * n
sum_c = 0
c = Counter(a)
for i, v in c.items():
    if v < 2:
        continue
    val = v * (v - 1) / 2
    dif[i] = v - 1
    sum_c += val
print('\n'.join([int(sum_c - data[i]) for i in a])

### FIXED CODE ###

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
dif = [0] * (n + 1)
sum_c = 0
c = Counter(a)
for i, v in c.items():
    if v < 2:
        continue
    val = v * (v - 1) / 2
    dif[i] = v - 1
    sum_c += val
print('\n'.join([str(int(sum_c - dif[i])) for i in a]))
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n = iinput()
ch = ["z"]+[chr(i) for i in range(ord("a"), ord("a")+25)]

def cnt26(num):
    cnt = 0
    while 1:
        if 26 ** cnt > num: return cnt - 1
        else: cnt += 1

s = ""
dig = cnt26(n)
while dig >= 1:
    div,mod = divmod(n, 26**dig)
    #print(div,mod)
    n = mod
    s += ch[div]
    dig -= 1
s += ch[mod]
print(s)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
import bisect as bs
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
def adj(n): return [[] for _ in range(n)]

n = iinput()
ch = ["z"]+[chr(i) for i in range(ord("a"), ord("a")+25)]

ans = ""
while n>0:
    if n%26: ans = ch[n%26] + ans; n //= 26
    else: ans = ch[n%26] + ans; n //= 26; n -= 1
print(ans)
# encoding: utf-8
import math
N = int(input())
A = list(map(int, input().split()))

def binsearch(seq, l, r, tar):
    # print("##", l, r, LmR[l:r + 1], tar)
    m = l + (r - l) // 2
    if l >= r: return l
    elif seq[m] < tar: return binsearch(seq, m + 1, r, tar)
    else: return binsearch(seq, l, m, tar)

Asum = [0]
tmp = 0
for Ai in A:
    tmp += Ai
    Asum.append(tmp)

LmR = []
for SAi in Asum[:-1]:
    LmR.append(-Asum[-1] + 2 * SAi)

ans = max(A) - min(A)
for b2 in range(2, N - 1):
    # b1
    # tar = -sum(A[b2:])
    tar = -(Asum[N] - Asum[b2])
    b1 = binsearch(LmR, 1, b2 - 1, tar)
    if tar - LmR[b1 - 1] < LmR[b1] - tar: b1 = max((1, b1 - 1))
    # escape
    if math.fabs((Asum[b2] - Asum[b1]) - (Asum[b1])) >= ans: continue
    # b3
    # tar = Asum[:b2]
    tar = Asum[b2]
    b3 = binsearch(LmR, b2 + 1, N - 1, tar)
    if tar - LmR[b3 - 1] < LmR[b3] - tar: b3 = max((b2 + 1, b3 - 1))
    parts = (Asum[b1], Asum[b2] - Asum[b1], Asum[b3] - Asum[b2], Asum[-1] - Asum[b3])
    # print("#", A[:b1], A[b1:b2], A[b2:b3], A[b3:], parts)
    if max(parts) - min(parts) < ans: ans = max(parts) - min(parts)
    
print(ans)

### FIXED CODE ###

# encoding: utf-8
N = int(input())
if N % 2: print(2 * N)
else: print(N)
i = input;i();print(sum([x-1 for x in i().split()]))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
print(sum(a) - n)
a,b = map(str, input().split())
if a < b:
	prinf('<')
elif a > b:
	print('>')
else:
	print('=')


### FIXED CODE ###

a,b = map(str, input().split())
if a == b:
	print('=')
elif a < b:
	print('<')
else:
	print('>')
D, N = map(int, input().split())
li = [i * 100 ** D for i in range(100)]
print(li[N])

### FIXED CODE ###

D, N = map(int, input().split())
li = []
cnt = 1
while len(li) < N:
    if cnt % 100 != 0:
        li.append(cnt * 100 ** D)
    cnt += 1

print(li[-1])
from math import pi
r = float(input())
print("{:.010f}{:.010f}".format(r*r*math.pi,2*r*math.pi))



### FIXED CODE ###

from math import pi
r = float(input())
print("{:.010f} {:.010f}".format(r * r * pi, 2 * pi * r))
1, y1, x2, y2 = list(map(int, input().split()))

xx = x2 - x1
yy = y2 - y1

x3 = x2 - yy
y3 = y2 + xx
x4 = x3 - xx
y4 = y3 - yy

print(x3, y3, x4, y4)

### FIXED CODE ###

x1, y1, x2, y2 = list(map(int, input().split()))

xx = x2 - x1
yy = y2 - y1

x3 = x2 - yy
y3 = y2 + xx
x4 = x3 - xx
y4 = y3 - yy

print(x3, y3, x4, y4)
n=int(input())
p=1
a=list(map(int,input().split()))

for i in range(n):
    p=p*a[i]
    
if p<= 10**18:
    print(p)
    
else:
    print(-1)

### FIXED CODE ###

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

c=a*b
print(c)
N = int(input())
L = list(map(int, input().split()))

L_sorted= L.sort()

target_num = N/2
if L_sorted[target_num-1] = L_sorted[target_num]
	print(0)
else:
  	print(L_sorted[target_num]-L_sorted[target_num-1])

### FIXED CODE ###

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

l.sort()
print(l[int(n/2)]-l[int(n/2)-1])
# -*- coding: utf-8 -*-



N, Q = map(int,input().split())
Node = []
Parsed = []
Counter = [0] * N
for i in range(N):
    Node.append([])
    Parsed.append([])

def parse(i):
    Parsed[i] += Node[i]
    for c in Node[i]:
        Parsed[i] += parse(c)
    #end for
    return Parsed[i]
        
for i in range(N-1):
    a, b = map(int,input().split())
    Node[a-1].append(b-1)
parse(0)
for i in range(N):
    Parsed[i].append(i)


for i in range(Q):
    p, x = map(int,input().split())
    for v in Parsed[p-1]:
        Counter[v] += x

print(" ".join(list(map(str,Counter))))



### FIXED CODE ###

# -*- coding: utf-8 -*-

N, Q = map(int,input().split())
Node = [-1] * N
Counter = [0] * N
Result = [0] * N

for i in range(N-1):
    a, b = map(int,input().split())
    Node[b-1] = a-1

for i in range(Q):
    p, x = map(int,input().split())
    Counter[p-1] += x

for i in range(N):
    p = i
    ans = 0
    while p >= i:
        ans += Counter[p]
        p = Node[p]
    Result[i] = ans
    if p >= 0:
        Result[i] += Result[p]

print(" ".join(list(map(str,Result))))
import math
from functools import reduce
def lcm(x,y):
  return(x*y)//math.gcd(x,y)

n=int(input())
A=list(map(int,input().split()))
num=reduce(lcm,A)
ans=0
def f(n):
  return sum(list(map(lambda x:n%x,A)))
print(f(num-1))

### FIXED CODE ###

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

m =1
for i in range(len(mods)):
  m *= mods[i]

sums = 0
for i in range(len(mods)):
  sums += (m-1) %mods[i]

print(sums)
from collections import deque
garage = deque()
while True:
    try:
        came = int(raw_input())
        if came == 0:
            print garage.pop()
        else:
            garage.append(came)
    except EOFError:
        break

### FIXED CODE ###

from collections import deque
garage = deque()
while True:
    try:
        came = int(raw_input())
        if came == 0:
            print garage.pop()
        else:
            garage.append(came)
    except ValueError:
        break
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]

def dfs(node,total,state,m):
    if visited[node]:
        return total,state,m
    state.append(C[node])
    nextM = max(total,total+C[node])
    total += C[node]
    visited[node] = True
    return dfs(P[node],total,state,nextM)

ans = -float('inf')

def calc(node):
    global visited,ans
    visited = [False for _ in range(N)]
    total,state,ma = dfs(P[node],0,[],-float('inf'))
    ans = max(ma,ans)
    K_ = K
    count = K // len(state)

    tmp = total * count
    for v in state[:K%len(state)]:
        tmp += v
    ans = max(ans,tmp)

    if total > 0:
        tmp = total * (count-1)
        for v in state:
            tmp += v
            ans = max(ans,tmp)






for i in range (N):
    calc(i)

print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]
cycle = []


ans = -float('inf')
for sn in range (N):
    cost = []
    nn = sn
    while True:
        cost.append(C[nn])
        nn = P[nn]
        if sn == nn:
            break
    total = sum(cost)
    l = len(cost)

    t = 0
    for i in range(l):
        t += cost[i]
        if i+1 > K: break
        now = t
        if total > 0:
            e = (K-i-1)//l
            now += total * e
        ans = max(ans,now)


print(int(ans))
import sys
from collections import defaultdict

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	al = list(IN())
	odd_dd=defaultdict(lambda : 0)
	even_dd=defaultdict(lambda :0)
	for i, v in enumerate(al):
		if i%2==0:
			odd_dd[v] += 1
		else:
			even_dd[v] += 1
	
	odd_ll=[(odd_dd[key], key) for key in odd_dd.keys()]
	even_ll=[(even_dd[key], key) for key in even_dd.keys()]
	
	odd_ll.sort(reverse=True)
	even_ll.sort(reverse=True)
	kk=n//2
	pa(odd_ll)
	pa(even_ll)
	#全部同じ
	if len(odd_ll)==1 and len(even_ll)==1:
		a=4/0
		if odd_ll[0][1]==even_ll[0][1]:
			return kk
		else:
			return 0
	
	if odd_ll[0][1] == even_ll[0][1]:
		if odd_ll[0][0] >= even_ll[0][0]:
			return (kk-odd_ll[0][0])+(kk-even_ll[1][0])
		else:
			return (kk-odd_ll[1][0])+(kk-even_ll[0][0])
	else:
		return (kk-odd_ll[0][0])+(kk-even_ll[0][0])
	
	#pa(odd_ll)
	#print(str(a+b+c)+s)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
from collections import defaultdict

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	al = list(IN())
	odd_dd=defaultdict(lambda : 0)
	odd_dd[-1]=0
	even_dd=defaultdict(lambda :0)
	even_dd[-1]=0
	
	for i, v in enumerate(al):
		if i%2==0:
			odd_dd[v] += 1
		else:
			even_dd[v] += 1
	
	odd_ll=[(odd_dd[key], key) for key in odd_dd.keys()]
	even_ll=[(even_dd[key], key) for key in even_dd.keys()]
	
	odd_ll.sort(reverse=True)
	even_ll.sort(reverse=True)
	kk=n//2
	pa(odd_ll)
	pa(even_ll)
	
	#先頭が同じ
	if odd_ll[0][1] == even_ll[0][1]:
		ra=(kk-odd_ll[0][0])+(kk-even_ll[1][0])
		rb=(kk-odd_ll[1][0])+(kk-even_ll[0][0])
		return min(ra, rb)
	else:
		ret= (kk-odd_ll[0][0])+(kk-even_ll[0][0])
		return ret
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

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

max = N
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)


### FIXED CODE ###

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2,max):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod

def COM(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k]*finv[n-k]%mod)%mod

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

max = N + M + K
fac = [0] * max
finv = [0] * max
inv = [0] * max
COMinit()
ans = 0
for i in range(K+1):
    c = COM(N-1,i)
    m = pow(M-1,N-i-1,mod)
    ans = (ans + ((c*m%mod)*M%mod))%mod
print(ans)
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-1):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

### FIXED CODE ###

from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-2):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)