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

from collections import deque
h,w = map(int, input().split())

m = [list(input()) for _ in range(h)]

def get_start_points(m):
    start_points = []
    for y in range(h):
        for x in range(w):
            if m[y][x] == '#':
                start_points.append((y,x))
    return start_points

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for q in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '#'
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(get_start_points(m)))

### FIXED CODE ###

from collections import deque
h,w = map(int, input().split())

m = [list(input()) for _ in range(h)]

def get_start_points(m):
    start_points = []
    for y in range(h):
        for x in range(w):
            if m[y][x] == '#':
                start_points.append((y,x))
    return start_points

def bfs(start_points):
    que = deque(start_points)
    step = 0
    count_flag = False
    while len(que):
        for q in range(len(que)):
            y,x = que.popleft()
            for dy,dx in [(1,0),(-1,0),(0,1),(0,-1)]:
                ny = y + dy
                nx = x + dx
                if not (0<=ny<h and 0<=nx<w) or m[ny][nx] != '.':
                    continue
                m[ny][nx] = '#'
                count_flag = True
                que.append((ny,nx))

        if count_flag:
            step += 1
            count_flag = False
        else:
            break
    return step

print(bfs(get_start_points(m)))
### BUGGY CODE ###

import numpy
N=int(input())
A=list(map(int,input().split()))
Ap=numpy.cumsum(A)
A2=[n*2 for n in Ap]
X=[sum(A)]*N
ans=0
C=[abs(x-y) for (x,y) in zip(X,A2)]
x=C.index(min(C))+1
pl=max(sum(A[:x]),sum(A[x:]))
mi=min(sum(A[:x]),sum(A[x:]))
while mi<pl:
  mi+=1
  ans+=1
  if mi==pl:
    break
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
p=q=sum(A)
for i in range(N):
  p-=2*A[i]
  q=min(abs(p),q)
print(q)
### BUGGY CODE ###

H, W = map(int, input().split(" "))

m = [ [-1 for x in range(W)] for y in range(H)]

count = 0
zero_coords = []
for y in range(H):
    line = list(input())
    for x, point in enumerate(line):
        if point == "#":
            m[y][x] = 0
            zero_coords.append([y, x])
            count += 1

tmp_coords = zero_coords
#mawari_soutais = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
mawari_soutais = [[-1, 0], [0, -1], [0, 1], [1, 0]]

val = 0
while count < H*W:
    val += 1
    new_tmp_coords = []
    for center_coord in tmp_coords:
        for mawari_soutai in mawari_soutais:
            mawari_coord = [mawari_soutai[i] + center_coord[i] for i in range(2)]
            y, x = mawari_coord
            if y < 0 or H <= y or x < 0 or W <= x or m[y][x] != -1:
                continue
            else:
                m[y][x] = val
                count += 1
                new_tmp_coords.append([y, x])
    tmp_coords = new_tmp_coords
    #print(m)

out = val
print(out)

### FIXED CODE ###

inputs = raw_input().replace("\n", "").split(" ")
H, W = map(int, inputs)

m = [ [-1 for x in range(W)] for y in range(H)]

count = 0
zero_coords = []
for y in range(H):
    #line = list(input())
    line = list(raw_input().replace("\n", ""))
    for x, point in enumerate(line):
        if point == "#":
            m[y][x] = 0
            zero_coords.append([y, x])
            count += 1

tmp_coords = zero_coords
#mawari_soutais = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]
mawari_soutais = [[-1, 0], [0, -1], [0, 1], [1, 0]]

val = 0
while count < H*W:
    val += 1
    new_tmp_coords = []
    for center_coord in tmp_coords:
        for mawari_soutai in mawari_soutais:
            mawari_coord = [mawari_soutai[i] + center_coord[i] for i in range(2)]
            y, x = mawari_coord
            if y < 0 or H <= y or x < 0 or W <= x or m[y][x] != -1:
                continue
            else:
                m[y][x] = val
                count += 1
                new_tmp_coords.append([y, x])
    tmp_coords = new_tmp_coords
    #print(m)

out = val
print(out)
### BUGGY CODE ###

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

Hyoten = [0] * (N-K+1)

for i in range(K,N+1):
  Hyoten[i-K] = 1
  for j in range(i-K,i):
    Hyoten[i-K] *= A[j]

for i in range(0,N-K+1):
  if i == 0:
    pre_Hyoten = Hyoten[i]
  else:
    if pre_Hyoten < Hyoten[i]:
      print("Yes")
    else:
      print("No")
      
    pre_Hyoten = Hyoten[i]



### FIXED CODE ###

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

for i in range(K+1,N+1):
  if A[i-K-1] < A[i-1]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

mod=10**9 + 7
#print(bin(9))
N=int(input())
A=list(map(int,input().split()))
A.sort()
#print(A)
A=[bin(i)[2:] for i in A]
#print(A)
nowdata=[0 for i in range(60)]
data=[0 for i in range(60)]

#print(A)

for i in range(N-1):
    S=A[i]

    for a in range(len(S)):
        if S[-a-1]=="1":
            nowdata[a]+=1
    S=A[i+1]
    for a in range(len(S)):
        if S[-a-1]=="0":
            data[a]+=nowdata[a]
        else:
            data[a]+=i+1-nowdata[a]
    #print(nowdata)


num=0
#print(data)
for i in range(60):
    num+=data[i]* (2**i)
    num%=mod

print(num)


### FIXED CODE ###

mod=10**9 + 7
#print(bin(9))
N=int(input())
A=list(map(int,input().split()))
A=[bin(i)[2:] for i in A]
A=[(60-len(i)) * "0" + i for i in A]
#print(A)
nowdata=[0 for i in range(60)]
data=[0 for i in range(60)]

#print(A)

for i in range(N-1):
    S=A[i]
    #print(nowdata)
    for a in range(len(S)):
        if S[a]=="1":
            nowdata[a]+=1
    S=A[i+1]
    for a in range(len(S)):
        if S[a]=="0":
            data[a]+=nowdata[a]
        else:
            data[a]+=i+1-nowdata[a]


num=0
#print(data)
for i in range(60):
    num+=data[-i-1]* (2**i)
    num%=mod

print(num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
n = int(input())
h = list(map(int, input().split()))
h.reverse()
r = 'Yes'
for i in range(n):
  for j in range(i+1, n):
    if h[j] > h[i] + 1:
      r = 'No'
      break
print(r)

### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n = int(input())
h = list(map(int, input().split()))
h.reverse()
limit = h[0]
r = 'Yes'
for i in range(n-1):
    if h[i] < limit:
      limit = h[i]
    if h[i+1] > limit + 1:
      r = 'No'
      break
    
print(r)
### BUGGY CODE ###

#!/usr/bin/env pypy3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import math,sys

n = int(sys.stdin.readline())
a = tuple(map(int,sys.stdin.readline().split()))
#n = int(input())
#a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
acc = a[0]
for i in range(n):
    acc = math.gcd(acc,a[i])
if acc != 1:
    print("not coprime")
    exit()

LIMIT=max(a)
minPrime = [0]*(LIMIT+1)
minPrime[1] = 1
def make():
    for i in range(2,LIMIT+1):
        if minPrime[i] == 0:
            minPrime[i] = i
            #print(i)
            for j in range(i+i,LIMIT+1,i):
                #print(i,j)
                if minPrime[j] == 0:
                    minPrime[j] = i
make()
def factrial(N):
     ret = []
     while minPrime[N] != N:
         ret.append(minPrime[N])
         N = N//minPrime[N]
     if N != 1:
         ret.append(N)
     return ret

judge = set([])
pc = True

pairwise = True
p = set() #all prime

for e in a:
    if not pairwise:
        break
    f = set(factrial(e))
    if p & f != set():
        pc = False
    #     #pairwise = False
    #     print("setwise coprime")
    #     exit(0)
    p = p | f
for i in a:
    if not pc:
        break
    asf = set(factrial(i))

    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import math
from collections import defaultdict
pc = True
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
for i in range(2,n):
    g = math.gcd(g,a[i])
M = max(a)
class Sieve_of_Eratosthenes:
    def __init__(self, N):
        self.sieve = [-1] * (N+1)
 
        for i in range(2,N+1):
            if self.sieve[i] == -1:
                for j in range(1,1+N//i):
                    self.sieve[i*j] = i
 
    def isprime(self, num):
        if num <= 1:
            return False
        else:
            return self.sieve[num] == num
 
    def factorization(self, num):
        ret = set([])
        while num != 1:
            div = self.sieve[num]
            ret.add(div)
            num //= div
        return ret
 
sofe = Sieve_of_Eratosthenes(M)
ddic = defaultdict()
judge = set([])
 
for i in a:
    if not pc:
        break
    asf = sofe.factorization(i)
    
    if judge & asf != set():
        pc = False
    judge |= asf
if pc:
    print("pairwise coprime")
elif g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def div10(d):
    return d//10
def rem2019(d):
    return d%2019
def resolve():
    S = sr()
    N = len(S)
    a = ['']
    for i in range(N):
        a.append(int(S[-1-i]+str(a[i])))
    a = a[::-1]
    a[-1] = 0
    ans = 0
    for i in range(N):
        t = list(map(rem2019, a))
        ans += Counter(t)[0]-1
        a = list(map(div10, a))
        g = a.pop()
    print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    S = sr()
    N = len(S)
    a = [0]*2019
    a[0] += 1
    t = 0
    r = 1
    for s in reversed(S):
        t += int(s)*r
        t %= 2019
        r *= 10
        r %= 2019
        a[t] += 1
    ans = 0
    for i in range(2019):
        ans += a[i]*(a[i]-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

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

    ans = 0
    for i in range(1, n):
        cnt = 0
        for j in range(n-i):
            if s[i+j] == s[j]:
                cnt += 1
            else:
                if cnt >= i:
                    ans = max(ans, i)
                    break
                else:
                    ans = max(ans, cnt)
                    cnt = 0

        ans = max(ans, min(cnt, i))

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
s = input()

n += 1
s += "#"

ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(n-i):
        if s[i+j] == s[j]:
            cnt += 1
        else:
            ans = max(ans, min(cnt, i))
            cnt = 0

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


def check_alloc(weights, cnt, cpct):	
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > cnt:
				return False
		else:
			cur += w	
	return True

n, k = map(int, input().split())
weights = [0] * n
cpct = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	cpct = max(cpct, weight)
	
while True:	
	can_alloc = check_alloc(weights, k, cpct)
	if can_alloc == False:
		cpct += 1
	else:
		break

print(cpct)



### FIXED CODE ###

import sys

def check_alloc(weights, k, cpct):
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > k or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = map(int, input().split())
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	w = int(input())
	weights[i] = w
	sum += w
	maxi = max(maxi, w)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
cpct = 0
while start <= end:
	cpct = int(start + (end - start) / 2)
	check = check_alloc(weights, k, cpct)
	if check == False:
		start = cpct + 1
	else:
		if start == end: break
		end = cpct
	
print(cpct)
### BUGGY CODE ###

import re
X = raw_input()
iter = 100000
pat = re.compile('(ST)')

for i in xrange(iter):
    s =	pat.search(X)
    if len(X) == 0:
	break
    if s is	not None:
    	X =	X.replace('ST','')
    else:
	break
print len(X)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    x = S()
    s_cnt = 0
    removed = 0
    for c in x:
        if c == 'S':
            s_cnt += 1
        if c == 'T':
            if s_cnt > 0:
                s_cnt -= 1
                removed += 2
    print(len(x) - removed)
main()
### BUGGY CODE ###

#coding:utf-8
from math import gcd
import itertools

def main():
    k = int(input())
    ans = 0
    num = [i for i in range(1,k+1)]
    comb = tuple(itertools.product(num, repeat=3))

    for i in comb:
        ans += gcd(gcd(i[0], i[1]), i[2])

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#coding:utf-8
from math import gcd

def main():
    k = int(input())
    ans = 0

    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += gcd(gcd(a, b), c)

    print(ans)

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

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    temp = list(range(1,N))
    if prev[a] != 0:
      del temp[G[a][prev[a]][1]-1]
    temp = deque(temp)
    for i,b in enumerate(G[a]):
      if seen[b] == 0:
        seen[b] = 1
        todo.append(b)
        prev[b] = a
        c = temp.popleft()
        colors.append((G[a][b][0],c))
        G[a][b][1]=G[b][a][1]=c
        if c > cmax: cmax = c
        
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])

### FIXED CODE ###

from collections import deque

N=int(input())
G=[{} for i in range(N+1)]
colors = []
for i in range(N-1):
  a,b=map(int,input().split())
  G[a][b]=[i,-1]
  G[b][a]=[i,-1]

def bfs(s):
  seen = [0 for i in range(N+1)]
  prev = [0 for i in range(N+1)]
  todo = deque([])
  cmax = 0
  now = s
  seen[now]=1
  todo.append(now)
  while 1:
    if len(todo)==0:break
    a = todo.popleft()
    if len(G[a])<50:
      if prev[a] == 0:
        a_color=set([])
      else:
        a_color=set([G[a][prev[a]][1]])
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          for c in range(1,N+1):
            if c not in a_color:
              a_color.add(c)
              colors.append((G[a][b][0],c))
              G[a][b][1]=G[b][a][1]=c
              if c > cmax: cmax = c
              break
    else:
      temp = list(range(1,N))
      if prev[a] != 0:
        del temp[G[a][prev[a]][1]-1]
      temp = deque(temp)
      for i,b in enumerate(G[a]):
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          prev[b] = a
          c = temp.popleft()
          colors.append((G[a][b][0],c))
          G[a][b][1]=G[b][a][1]=c
          if c > cmax: cmax = c
            
  return colors, cmax

colors,cmax = bfs(1)
colors=sorted(colors)

print(cmax)
for i in range(N-1):
  print(colors[i][1])
### BUGGY CODE ###

n, q = map(int, input().split())
S = input()
ans = []
for i in range(q):
    l, r = map(int, input().split())
    s = S.count("AC", l-1, r)
    ans.append(s)
for i in ans:
    print(i)

### FIXED CODE ###

n, q = map(int, input().split())
S = input()
lr = []
s = [0]*(n+1)
count = 0

for i in range(q):
    LR = list(map(int, input().split()))
    lr.append(LR)

for i in range(n-1):
    if S[i:i+2] == "AC":
        count += 1
        s[i+1] = count
    else:
        s[i+1] = s[i]
        
for i in range(q):
    print(s[lr[i][1] - 1] - s[lr[i][0] - 1])
### BUGGY CODE ###

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

MOD = 10 ** 9 + 7
M = 200005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * rfact[n - k] * rfact[k] % MOD


num = [0] * 200005
f = [0] * 200005
for i in range(W):
    q = pow(pow(2, i + B), MOD - 2, MOD) * comb(i + B - 1, B - 1) % MOD
    f[i + B] = q

g = [0] * 200005
for i in range(B):
    q = pow(pow(2, i + W), MOD - 2, MOD) * comb(i + W - 1, W - 1) % MOD
    g[i + W] = q
    num[i + W + 1] = q

pB, pW = 0, 0
for i in range(1, B + W + 1):
    d = 1 - (pB + pW) + 2 * MOD
    d %= MOD
    pB += f[i]
    pB %= MOD
    pW += g[i]
    pW %= MOD

    num[i] += num[i - 1]
    num[i] %= MOD
    print((pow(2, MOD - 2, MOD) * d + num[i]) % MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7
M = 200005
fact = [0] * M
fact[0] = 1
for i in range(1, M):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * M
rfact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(M - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD

pow2 = [0] * M
pow2[0] = 1
for i in range(1, M):
    pow2[i] = pow2[i - 1] * 2
    pow2[i] %= MOD


def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * rfact[n - k] * rfact[k] % MOD


num = [0] * 200005
f = [0] * 200005
for i in range(W):
    q = pow(pow2[i + B], MOD - 2, MOD) * comb(i + B - 1, B - 1) % MOD
    f[i + B] = q

g = [0] * 200005
for i in range(B):
    q = pow(pow2[i + W], MOD - 2, MOD) * comb(i + W - 1, W - 1) % MOD
    g[i + W] = q
    num[i + W + 1] = q


inv2 = pow(2, MOD - 2, MOD)
pB, pW = 0, 0
for i in range(1, B + W + 1):
    d = 1 - (pB + pW) + 2 * MOD
    d %= MOD
    pB += f[i]
    pB %= MOD
    pW += g[i]
    pW %= MOD

    num[i] += num[i - 1]
    num[i] %= MOD
    print((inv2 * d + num[i]) % MOD)
### BUGGY CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = [0 for j in range(N)]
Z =[0]*N

for i in range(N):
    H.append(lines[1].split(' ')[i])

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if Y[A-1] < int(H[B-1]):
      Y[A-1] = int(H[B-1])
    if Y[B-1] < int(H[A-1]):
      Y[B-1] = int(H[A-1])

good = 0
for i in range(N):
    if Y[i] ==0:
        good +=1
    else:
        if int(H[i]) > int(Y[i]):
        	good +=1

print(good)


### FIXED CODE ###

import sys

lines = sys.stdin.readlines()

X = lines[0].split(' ')
N = int(X[0])
M = int(X[1])

H = []
Y = []

H=lines[1].split(' ')

for j in range(M):
    A = int(lines[j+2].split(' ')[0])
    B = int(lines[j+2].split(' ')[1])
    if int(H[A-1]) <= int(H[B-1]):      
      Y.append(A-1)
    if int(H[B-1]) <= int(H[A-1]):
      Y.append(B-1)
Z = len(set(Y))
print(N-Z)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


def solve(g, f, fi, m):
    def dfs(pre, cur, memo, m):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt, memo, m)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    memo = {}
    print(*[dfs(None, i, memo, m)[1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]
    mod = 10**9 + 7

    fact = [1] * (n+1)
    fact_inv = [1] * (n+1)

    for i in range(1, n+1):
        fact[i] = fact[i-1] * i % mod

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(1, n)[::-1]:
        fact_inv[i] = fact_inv[i+1] * (i+1) % mod

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

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

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

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

    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()
### BUGGY CODE ###

N = int(input())
hlist = list(map(int, input().split()))
cost = [-1 for _ in range(N)]
cost[0] = 0
cost[1] = abs(hlist[1] - hlist[0])
#再帰
"""
def function(n)
if 終了条件 return 初項
return function(n-1)を処理したもの
"""
def dp(n):
  #print(n)
  if n==0: return cost[0]
  if n==1: return cost[1]
  else: return min(dp(n-1)+abs(hlist[n]-hlist[n-1]), dp(n-2)+abs(hlist[n]-hlist[n-2]))

for i in range(N):
  cost[i] = dp(i)
print(cost[-1])

### FIXED CODE ###

N = int(input())
hlist = list(map(int, input().split()))
cost = [-1 for _ in range(N)]

def dp(n):
  if n==0: return 0
  if n==1: return abs(hlist[1] - hlist[0])
  else: return min(cost[n-1]+abs(hlist[n]-hlist[n-1]), cost[n-2]+abs(hlist[n]-hlist[n-2]))

for i in range(N):
  cost[i]=dp(i)
print(cost[-1])
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
i = 1
dp = [0 for i in range(N)]
 
while not i==N:
    l = min(K,i)
    data = [dp[i-j]+abs(h[i] - h[i-j]) for j in range(1,l+1)]
    dp[i] = min(data)
    i+=1
    
print(dp[N-1])

### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()