Harryxun/stf_run huggingface dataset:
from sys import exit
from collections import defaultdict
import itertools
H,W,N = [int(n) for n in input().split()]
Sr,Sc = [int(n) for n in input().split()]
#上に
Uout = H-Sr + 1
#下に
Dout = Sr
#右に落とすのに必要な歩数
Rout = W - Sc + 1
#左に
Lout = Sc
S = str(input())
T = str(input())

def check(outcnt, C, A, lim, B):
    re = False
    for s,t in zip(S,T):
        if s == B and outcnt == lim -1:
            re = True
            break
        if( s == C):
            outcnt -= 1
        if(outcnt == 0 ):
            print("NO")
            exit()
        if(t == A and outcnt < lim):
            outcnt += 1
    if(re):
        check(outcnt, C, A, lim-1, B)
check(Rout, "R", "L", W, "L")
check(Lout, "L", "R", W, "R")
check(Uout, "U", "D", H, "D")
check(Dout, "D", "U", H, "U")
print("YES")


### FIXED CODE ###

from sys import exit
from collections import defaultdict
H,W,N = [int(n) for n in input().split()]
Sr,Sc = [int(n) for n in input().split()]
#上に
Dout = H-Sr + 1
#下に
Uout = Sr
#右に落とすのに必要な歩数
Rout = W - Sc + 1
#左に
Lout = Sc
# print(Uout, Dout,Rout, Lout)
S = str(input())
T = str(input())
ptrC = defaultdict(int)
ptrA = defaultdict(int)
for s,t in zip(S,T):
    ptrC[s]+=1
    ptrA[t]+=1
# print(ptrC,ptrA)
# if ptrC["R"] - ptrA["L"] >= Rout or ptrC["L"] - ptrA["R"] >= Lout or ptrC["D"] - ptrA["U"] >= Dout or ptrC["U"] - ptrA["D"] >= Uout:
#     print("NO")
#     exit()
def check(outcnt, C, A, lim, B):
    backed = 0
    for s,t in zip(S,T):
        if s == B and outcnt == lim -1 and backed > 0:
            outcnt -= 1
            backed -= 1
        if( s == C ):
            outcnt -= 1
        if( outcnt == 0 ):
            print("NO")
            exit()
        if( t == A and outcnt < lim ):
            outcnt += 1
            backed += 1

check(Rout, "R", "L", W, "L")
check(Lout, "L", "R", W, "R")
check(Uout, "U", "D", H, "D")
check(Dout, "D", "U", H, "U")
print("YES")
N = int(input())
d = list(map(int, input().split()))


def combinations(d, tmp_out, i, j):
    if (j >= N):
        i += 1
        j = i + 1
        if (i >= N):
            return tmp_out
        elif (j >= N):
            return tmp_out
    if (j >= N) or (i >= N):
        return tmp_out
    else:
        tmp_out += d[i] * d[j]
        return combinations(d, tmp_out, i, j + 1)


out = combinations(d, 0, 0, 1)

print(out)

### FIXED CODE ###

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

out = 0
for i in range(N):
    for j in range(i + 1, N):
        out += d[i] * d[j]

print(out)
import sympy



def main():
    n = int(input())

    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n+1):
        dp[i] = dp[i-1] + len(sympy.divisors(i-1))

    print(dp[-1])


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    for a in range(1, n):
        ans += (n-1) // a
    print(ans)

if __name__ == '__main__':
    main()
import sys

from collections import Counter

n = int(input())

v = []
v1 = []
v2 = []

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

for i in range(int(n/2)):
    v1.append(v[2*i])
    v2.append(v[2*i+1])

e = Counter(v1)
o = Counter(v2)

ee = e.most_common(2)
oo = o.most_common(2)

if ee[0][0] != oo[0][0]:
    print(n - (ee[0][1]+oo[0][1]))
    sys.exit()

if ee[0][0] == oo[0][0]:
    if len(ee) == 1 and len(oo) == 1:
        print(n - (ee[0][1]))
        sys.exit()

    if len(ee) == 1:
        print(n - (ee[0][1]+oo[1][1]))
        sys.exit()

    if len(oo) == 1:
        print(n - (ee[1][1]+oo[0][1]))
        sys.exit()

    if ee[0][1] == oo[0][1]:
        print(n - (ee[0][1] + min(ee[1][1],oo[1][1])))
    
    if ee[0][1] > oo[0][1]:
        print(n - (ee[0][1]+oo[1][1]))
        sys.exit()
    else:
        print(n - (ee[1][1]+oo[0][1]))
        sys.exit()


### FIXED CODE ###

i = input()

k = []

for j in i:
    if j == '1':
        k.append('9')
    else:
        k.append('1')

print(''.join(k))
import math

a, b = input().split()
A = int(a)
B = float(b)

print(int(ath.floor(A*B)))

### FIXED CODE ###

a, b = input().split()
A = int(a)
B = float(b)
B100 = round(100*B)

C=A*B100
print(str(C//100))
D,T,S=map(int,input())
if D*S>T:
	print("No")
else:
	print("Yes")

### FIXED CODE ###

D,T,S=map(int,input().split())
if (D/S)>T:
	print("No")
else:
	print("Yes")
import math
A,B,C,D = map(int, input().split())


t = math.gcd(C, D)

m = math.floor(B / C) + math.floor(B / D) - math.floor(B / t)
 
n = math.floor((A-1) / C) + math.floor((A-1) / D ) - math.floor((A-1) / t)

print(B-A+1-m+n)
 

### FIXED CODE ###

from fractions import gcd
 
A, B, C, D = map(int, input().split())
t = C * D // gcd(C, D)
print((B - (A - 1)) - (B//C + B//D - B//t) + ((A-1)//C + (A-1)//D - (A-1)//t))
#import math
# a,b =[int(i) for i in input().split()]

r=int(input())
#r=2
pi=3.141592653589793
A=[pi*r**2,2*pi*r]
print("{0:.5f} {1:.5f}".format(A[0],A[1]))

### FIXED CODE ###

#import math
# a,b =[int(i) for i in input().split()]

r=float(input())
#r=2
pi=3.141592653589793
A=[pi*r**2,2*pi*r]
print("{0:.5f} {1:.5f}".format(A[0],A[1]))
a, b, c = map(int, input().split())

if b > a:
    temp = a
    a = b
    b = temp

res = c - a
res = res - b
temp = 4*a*b

if res**2 > temp:
    print ("Yes")
else:
    print ("No")



### FIXED CODE ###

N = int(raw_input())

char_list = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

prev = ["a"]

for i in range(1, N):
    temp = []
    for item in prev:
        item_list = []
        for j in range(len(item)):
            item_list.append(item[j])
        num_char = len(set(item_list))
        for j in range(num_char+1):
            temp.append(item+char_list[j])

    prev = temp


print ' '.join(map(str, prev))
while True:
  count = input()
  if count == 0: break
  previous_cube = [ 1, 2, 3, 4, 5, 6]
  operation = {'North':[1, 5, 2, 3, 0, 4], 'East':[3, 1, 0, 5, 4, 2], 'West': [2, 1, 5, 0, 4, 3], 'South':[4, 0, 2, 3, 5, 1], 'Right':[0, 2, 4, 1, 3, 5], 'Left':[0, 3, 1, 4, 2, 5]}
  sum = 1
  for i in xrange(count):
    new_cube = []
    for e in xrange(5):
      new_cube.append(previous_cube[operation[raw_input()][e]])
    sum += new_cube[0]
    previous_cube = new_cube
  print sum

### FIXED CODE ###

while 1:
  n = input()
  if n == 0:  break
  d = range(1, 7)
  ans = 1
  for i in range(n):
    c = raw_input()[0]
    if c == 'N': S = [1,5,2,3,0,4]
    elif c == "S": S = [4,0,2,3,5,1]
    elif c == "E": S = [3,1,0,5,4,2]
    elif c == "W": S = [2,1,5,0,4,3]
    elif c == "R": S = [0,2,4,1,3,5]
    elif c == "L": S = [0,3,1,4,2,5]
    d = [d[s] for s in S]
    ans += d[0]
  print ans
N,M = map(int,input().split())

RES = []

for i in range(M):
    RES.append(list(input().split()))

WA = [0]*(M+3) ##WAするのは提出数
ACed = [0]*(N+3) ##ACするのは問題数

for i in range(M):
    num = int(RES[i][0])
    if RES[i][1] == "WA" and not ACed[num]:
        WA[num] += 1
    elif RES[i][1] == "AC":
        ACed[num] = 1

print(sum(ACed),end=" ")
print(sum(WA))

### FIXED CODE ###

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

RES = []

for i in range(M):
    RES.append(list(input().split()))

WA = [0]*(M+N)
ACed = [0]*(N+M)
tmp_num = [0]*(M+N)
tmp = 0
for i in range(M):
    num = int(RES[i][0])
    if RES[i][1] == "WA" and not ACed[num]:
        tmp_num[num] += 1
    elif RES[i][1] == "WA" and ACed[num]:
        tmp += 1
    else:
        ACed[num] = 1
        WA[num] = tmp_num[num]

print(sum(ACed),end=" ")
print(sum(WA))
import math
s = int(input())
print(s * 2 * math.pie)

### FIXED CODE ###

import math
s = int(input())
print(s * 2 * math.pi)
n, k = map(int, input().split())
alst = list(map(int, input().split()))

l = 0
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)

### FIXED CODE ###

n, k = map(int, input().split())
alst = list(map(int, input().split()))

if k == 0:
    print(max(alst))
    exit()

l = 1
r = max(alst)

while r != l:
    pos = (r + l) // 2
    cnt = 0
    for a in alst:
        cnt += (a - 1) // pos
    if cnt <= k:
        r = pos
    else:
        l = pos + 1
print(r)
from sys import stdin

h,n = [int(x) for x in stdin.readline().rstrip().split()]
a = [0]*n ;b = [0]*n

for i in range(n):
    a[i],b[i] = [int(x) for x in stdin.readline().rstrip().split()]

#最高で削られる可能性がある体力
H = max(a)

inf = 10**10

#体力をちょうどi削るために必要な最低の魔力
dp = [inf for _ in range(h+H+1)];dp[0] = 0

for i in range(n):
    for j in range(h+1):
        if dp[j+a[i]] > dp[j] + b[i]:
            dp[j+a[i]] = dp[j] + b[i]

print(min(dp[h:]))

### FIXED CODE ###

from sys import stdin
import math
a,b = [int(x) for x in stdin.readline().rstrip().split()]
print(math.ceil(a/b))
n = int(input())
s = list(map(int,input().split()))
s.sort()
sum = 0

for i in range(0,2n,2):
  sum += s[i]
print(sum)

### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
s.sort()
sum = 0

for i in range(0,2*n,2):
  sum += s[i]
print(sum)
import heapq
n = int(input())
xs = list(map(int, input().split()))
head = heapq.heapify(xs[:n])
body = xs[n:2*n]
body_and_tail = sorted(xs[n:])
sum_tail = sum(body_and_tail_list[:n])
unused_tail = heapq.heapify(body_and_tail[-n:])
ans = -1000000000000000000000
temp = sum(head) - sum_tail
for b in body:
    heapq.push(head, b)
    temp = temp - heapq.pop(head) - heapq.pop(unused_tail) + 2*b
    ans = max(ans, temp)
print(ans)

### FIXED CODE ###

import heapq
n = int(input())
xs = list(map(int, input().split()))
head = [(x, x) for x in xs[:n]]
heapq.heapify(head)
body = xs[n:-n]
tail = [(-x, x) for x in xs[-n:]]
heapq.heapify(tail)

def f(heap, body, sign, initial):
    answer = [initial]
    acc = initial
    for b in body:
        heapq.heappush(heap, (sign*b, b))
        _, x = heapq.heappop(heap)
        acc = acc + b - x
        answer.append(acc)
    return answer
 
print(max(x - y for x, y in zip(
    f(head, body, 1, sum(xs[:n])),
    f(tail, body[::-1], -1, sum(xs[-n:]))[::-1])))
import math

a, b = map(int, input().split())
print(a//math.gcd(a, b)*b)


### FIXED CODE ###

def gcd(a, b):
    if not b:
        return a
    return gcd(b, a % b)

a, b = map(int, input().split())
print(a//gcd(a, b)*b)
N = int(input())
S = [input() for i in range(N)]

COUNT = S.count("Y")

if COUNT > 0:
  print("Four")
else:
  print("Three")
    
    


### FIXED CODE ###

N = int(input())
S = list(input().split())

COUNT = S.count("Y")

if COUNT > 0:
  print("Four")
else:
  print("Three")
#156d
n,a,b = map(int, input().split())

##############################################
#https://tane-no-blog.com/976/
mod = pow(10, 9) + 7
 
def comb(N, x):
    #n*(n-1)*…*(n-1+1)を計算
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    
    #a!を計算 
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
        
    #最後の項 a!**((10**9+7)-2)を計算
    d = pow(denominator, mod-2, mod)
    
    return numerator * d

################################

comb_all = pow(2,n,MOD_BY) - 1 #(2**n) - 1
comb_a = comb(n,a)
comb_b = comb(n,b)

#print(comb_all,comb_a,comb_b)
print((comb_all-comb_a-comb_b)%MOD_BY)

### FIXED CODE ###

#156d
n,a,b = map(int, input().split())

##############################################
#https://tane-no-blog.com/976/
mod = pow(10, 9) + 7
 
def comb(N, x):
    #n*(n-1)*…*(n-1+1)を計算
    numerator = 1
    for i in range(N-x+1, N+1):
        numerator = numerator * i % mod
    
    #a!を計算 
    denominator = 1
    for j in range(1, x+1):
        denominator = denominator * j % mod
        
    #最後の項 a!**((10**9+7)-2)を計算
    d = pow(denominator, mod-2, mod)
    
    return numerator * d

################################

comb_all = pow(2,n,mod) - 1 #(2**n) - 1
comb_a = comb(n,a)
comb_b = comb(n,b)

#print(comb_all,comb_a,comb_b)
print((comb_all-comb_a-comb_b)%mod)
A , B = map(int , input().split())

if A > B + 1:
	print(2*A - 1)
elif B > A + 1:
	print(2*b - 1)
else:
	print(A + B)




### FIXED CODE ###

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

if A > B + 1:
	print(2*A - 1)
elif B > A + 1:
	print(2*B - 1)
else:
	print(A + B)
n,k,x,y=map(int, input().split())
tmp=0
if n>=k:
    print(x*k+y*(n-k))
else:
    print(x*n)
        

### FIXED CODE ###

n=int(input())
k=int(input())
x=int(input())
y=int(input())
print(min(n,k)*x+max(n-k,0)*y)
S = input()

if
(S[0]==S[1] and S[2]==S[3] and S[0]!=S[2]) or
(S[0]==S[2] and S[1]==S[3] and S[0]!=S[1]) or
(S[0]==S[3] and S[1]==S[2] and S[0]!=S[2]):
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

S = input()

if (S[0]==S[1] and S[2]==S[3] and S[0]!=S[2]) or \
(S[0]==S[2] and S[1]==S[3] and S[0]!=S[1]) or \
(S[0]==S[3] and S[1]==S[2] and S[0]!=S[2]):
  print("Yes")
else:
  print("No")
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n-1)]

neighbor = [[] for _ in range(n+1)]
for edge in lst:
    neighbor[edge[0]].append((edge[1], edge[2]))
    neighbor[edge[1]].append((edge[0], edge[2]))

    
color = [-1] * (n+1)

#startをbwで塗る
def dfs(start, bw):
    color[start] = bw
    for pair in neighbor[start]:
        if color[pair[0]] != -1:
            continue
        elif pair[1] % 2 == 0:
            dfs(pair[0], bw)
        else:
            dfs(pair[0], (bw + 1) % 2)

for i in range(1, n+1):
    if color[i] == -1:
        dfs(i, 0)
        
for i in range(1, n+1):
    print(color[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
lst = [list(map(int, input().split())) for _ in range(n-1)]

neighbor = [[] for _ in range(n+1)]
for edge in lst:
    neighbor[edge[0]].append((edge[1], edge[2]))
    neighbor[edge[1]].append((edge[0], edge[2]))

    
color = [-1] * (n+1)

#startをbwで塗る
def dfs(start, bw):
    color[start] = bw
    for pair in neighbor[start]:
        if color[pair[0]] != -1:
            continue
        elif pair[1] % 2 == 0:
            dfs(pair[0], bw)
        else:
            dfs(pair[0], (bw + 1) % 2)

dfs(1, 0)
        
for i in range(1, n+1):
    print(color[i])
n = int(input())
H = [int(h) for h in input().split()]

result = []
count = 0
for i in range(n-1):
  if (H[i]>=H[i+1]):
    count+=1
    if(i == n-2):
      result.append(count)
  else:
    result.append(count)
    count=0
    
print(max(result))

### FIXED CODE ###

n = int(input())
H = [int(h) for h in input().split()]

result = []
count = 0
if(n==1):
  print(0)
  exit()

for i in range(n-1):
  if (H[i]>=H[i+1]):
    count+=1
    if(i == n-2):
      result.append(count)
  else:
    result.append(count)
    count=0
    
print(max(result))
A, B = map(int, input().split(" "))
if 1 <= A, B <= 9:
    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())
_ = [list(map(int, input().split())) for _ in range(n)]
_.insert(0, [0, 0, 0])

dt = [_[i + 1][0] - _[i][0] for i in range(n)]
dx = [_[i + 1][1] - _[i][1] for i in range(n)]
dy = [_[i + 1][2] - _[i][2] for i in range(n)]

ans = "Yes"

for i in range(n):
    man_d = abs(dx[i]) + abs(dy[i])
    if not (dt[i] >= man_d and (dt [i]- man_d) % 2 == 0):
        ans = "No"

print(ans)

### FIXED CODE ###

a, b=map(int,input().split())
print("Even" if a * b % 2 == 0 else "Odd")
from collections import deque


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == ".":
                dist = [[-1] * W for _ in range(H)]
                dist[i][j] = 0
                que = deque()
                que.append([i, j])

                while que:
                    y, x = que.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx >= W or nx < 0 or ny >= H or ny < 0:
                            continue
                        if dist[ny][nx] != -1:
                            continue
                        if maze[ny][nx] == "#":
                            continue
                        dist[ny][nx] = dist[y][x] + 1
                        que.append([ny, nx])
            
            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

H, W = map(int, input().split())
maze = [input() for _ in range(H)]


def solve():
    ans = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] == ".":
                dist = [[-1] * W for _ in range(H)]
                dist[i][j] = 0
                que = deque()
                que.append([i, j])

                while que:
                    y, x = que.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        if nx >= W or nx < 0 or ny >= H or ny < 0:
                            continue
                        if dist[ny][nx] != -1:
                            continue
                        if maze[ny][nx] == "#":
                            continue
                        dist[ny][nx] = dist[y][x] + 1
                        que.append([ny, nx])
            else:
                continue
            ans = max(ans, max(max(steps) for steps in dist))
    print(ans)


if __name__ == "__main__":
    solve()
import math
def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"

def merge(list_a, left, mid, right):
    import math
    n1 = mid - left
    n2 = right - mid
    list_l = []
    list_r = []
    for i in range(0,n1):
        list_l.append(list_a[left + i])
    for i in range(0,n2):
        list_r.append(list_a[mid + i])
    list_l.append(math.inf)
    list_r.append(math.inf)
    i = 0
    j = 0
    for k in range(left,right):
        if list_l[i] <= list_r[j]:
            list_a[k] = list_l[i]
            i += 1
        else:
            list_a[k] = list_r[j]
            j += 1

def mergeSort(list_a, left, right):
    if left + 1 < right:
        mid = (left + right) //2
        mergeSort(list_a, left, mid)
        mergeSort(list_a, mid, right)
        merge(list_a, left, mid, right)


n = int(input())
list_d = list((map(int, input().split())))
m = int(input())
list_t = list((map(int, input().split())))

mergeSort(list_d, 0, n)

for number in list_t:
    ind = binarySearch(list_d, number)
    if ind != "NOT_FOUND":
        del list_d[ind]
    else:
        print("NO")
        break
else:
    print("YES")


### FIXED CODE ###

n = int(input())
list_d = list((map(int, input().split())))
m = int(input())
list_t = list((map(int, input().split())))

dict_d = {}
dict_t = {}
for number in set(list_d):
    dict_d[number] = 0
for number in set(list_t):
    dict_d[number] = 0
for number in list_d:
    dict_d[number] += 1

for number in set(list_t):
    dict_t[number] = 0
for number in list_t:
    dict_t[number] += 1

for number,value in dict_t.items():
    if dict_d[number] < value:
        print("NO")
        break
    else:
        pass
else:
    print("YES")
H, W, N = map(int, input().split())
sr, sc = map(int, input().split())
S = input()
T = input()

flag = 0
hidari = sc
migi = sc
ue = sr
shita = sr
for i in range(N):
  if S[i] == 'L':
    hidari -= 1
  if S[i] == 'R':
    migi += 1
  if S[i] == 'U':
    ue -= 1
  if S[i] == 'D':
    shita += 1
  if hidari == 0 or migi == W+1 or ue == 0 or shita == H+1 :
    flag = 1
  
  if T[i] == 'R' and hidari != W:
    hidari += 1
  if T[i] == 'L' and migi != 1:
    migi -= 1
  if T[i] == 'D' and ue != 1:
    ue += 1
  if T[i] == 'U' and shita != H:
    shita -= 1

if flag :
  print("NO")
else :
  print("YES")
  

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]

dx = [1,-1,0,0]

dy = [0,0,1,-1]
B = [[-1 for i in range(W)] for j in range(H)]
qu = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      B[i][j] = 0
      qu.append((i,j))
      
      
while qu:
  base = qu.popleft()
  for i in range(4):
    if base[0]+dx[i] < 0 or base[0]+dx[i] >=H or base[1]+dy[i] < 0 or base[1]+dy[i] >=W:
      continue
    if B[base[0]+dx[i]][base[1]+dy[i]] == -1:#未訪問
      qu.append((base[0]+dx[i],base[1]+dy[i]))
      B[base[0]+dx[i]][base[1]+dy[i]] = B[base[0]][base[1]] + 1
      
ans = 0
for i in range(H):
  ans = max(ans,max(B[i]))
print(ans)
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int n,k;
  cin>>n>>k;
  
  if (n==1){
    cout<<k<<endl;
  }
  else {
    cout<<k*pow(k-1,n-1)<<endl;
  }
}


### FIXED CODE ###

n,k=map(int,input().split())
if n==1:
  print(k)
else:
  print(k*(k-1)**(n-1))
N = int(input())
A = [int(n) for n in input().split()]

def main():
    a = sorted(A)
    odd = N % 2 != 0
    if odd:
        a = list(map(lambda t: t[1] if t[0] % 2 == 0 else t[1] - 1, enumerate(a)))
    else:
        a = list(map(lambda t: t[1] - 1 if t[0] % 2 == 0 else t[1], enumerate(a)))
    passed = a == list(range(N))
    if passed:
        base = N - 1 if odd else N
        ans = int(2 ** (base / 2)) % 1000000007
    else:
        ans = 0
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
A = [int(n) for n in input().split()]

def main():
    d = {}
    for a in A:
        if a not in d:
            d[a] = 0
        d[a] += 1
    ks =  all(map(lambda k: k % 2 == 0, d.keys())) or all(map(lambda k: k % 2 != 0, d.keys()))
    if 0 in d:
        d[0] += 1
    vs = all(map(lambda v: v == 2, d.values()))

    if ks and vs:
        n = N if N % 2 == 0 else N - 1
        n //= 2
        ans = 1
        for _ in range(n):
            ans *= 2
            ans %= 1000000007
    else:
        ans = 0
    print(ans)

if __name__ == '__main__':
    main()
from itertools import combinations
import sys
sys.setrecursionlimit(10**6)

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

comb = list(combinations(d, 2))
ans = 0

for i in range(len(d)):
    ans += comb[i][0] * comb[i][1]

print(ans)

### FIXED CODE ###

from itertools import combinations

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

comb = list(combinations(d, 2))

ans = 0

for i in range(len(comb)):
    ans += comb[i][0] * comb[i][1]
    # print(ans, comb[i])

print(ans)
l = list(map(int, input().split()))

while(l != []):
    length = len(str(l[0]+l[1]))
    print(length)
    l = list(map(int, input().split()))


### FIXED CODE ###

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

while(l != []):
    try:
        length = len(str(l[0]+l[1]))
        print(length)
        l = list(map(int, input().split()))
    except:
        break
s,t=0,-1
for _ in range(int(input())):
    a,b,c=map(int,input().split())
    if t==1:
        if b>=c:
            s+=b
            t=2
        else:
            s+=c
            t=3
    elif t==2:
        if a>=c:
            s+=a
            t=1
        else:
            s+=c
            t=3
    elif t==3:
        if a>=b:
            s+=a
            t=1
        else:
            s+=b
            t=2
    else:
        if a>=b and a>=c:
            s=a
            t=1
        elif b>=c:
          	s=b
            t=2
        else:
          	s=c
            t=3
print(s)


### FIXED CODE ###

n,l=int(input()),list(map(int,input().split()))
c1,c2=0,abs(l[0]-l[1])
for i in range(2,n):
  t=c2
  c2=min(c1+abs(l[i]-l[i-2]),c2+abs(l[i]-l[i-1]))
  c1=t
print(c2)