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

from collections import deque
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
same = set()
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
    if uf.parents.count(-1*N) == 1:
        break
print(ans)

### FIXED CODE ###

from collections import deque
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        
N = int(input())
xseq = []
yseq = []
uf = UnionFind(N)
ans = 0

for i in range(N):
    x,y = (int(x) for x in input().split())
    xseq.append((x,i))
    yseq.append((y,i))
xseq.sort()
yseq.sort()
xdiff = [(xseq[i][0]-xseq[i-1][0],(xseq[i][1],xseq[i-1][1])) for i in range(1,N)]
ydiff = [(yseq[i][0]-yseq[i-1][0],(yseq[i][1],yseq[i-1][1])) for i in range(1,N)]
diff = xdiff + ydiff
diff.sort()
d = deque(diff)

for i in range(len(d)):
    temp = d.popleft()
    if uf.find(temp[1][0]) != uf.find(temp[1][1]):
        uf.union(temp[1][0],temp[1][1])
        ans += temp[0]
print(ans)
### BUGGY CODE ###

import itertools

K,S = list(map(int,input().split()))
l = set(range(K+1))
ans = 0

for x, y, z in itertools.product(l,l,l):
    if x + y + z == S:
        ans += 1

print(ans)

### FIXED CODE ###

import itertools

K,S = list(map(int,input().split()))
l = set(range(K+1))
ans = 0

for x, y in itertools.product(l,l):
    if x + y + K >= S and x + y <= S:
        ans += 1

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

from functools import reduce

# 2数の最大公約数
def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

# リストの最大公約数
def gcd_list(nums):
    return reduce(gcd, nums)

# 入力
n = int(input())
a = list(map(int, input().split()))

#a[i]より前方要素の最大公約数を保持
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd_list(a[0:i])
# print(l)

#a[i]より後方要素の最大公約数を保持
r = [0 for _ in range(n)]
r[n-1] = 0
for i in range(0, n-1):
    r[i] = gcd_list(a[i+1:n])
# print(r)

# a[i]を除いた最大公約数を計算
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

# 出力
print(ans)

### FIXED CODE ###

from functools import reduce

# 2数の最大公約数
def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

# リストの最大公約数
def gcd_list(nums):
    return reduce(gcd, nums)

# 入力
n = int(input())
a = list(map(int, input().split()))

#a[i]より前方要素の最大公約数を保持
l = [0 for _ in range(n)]
l[0] = 0
for i in range(1, n):
    l[i] = gcd(l[i-1], a[i-1])
# print(l)

#a[i]より後方要素の最大公約数を保持
r = [0 for _ in range(n)]
r[n-1] = 0
for i in reversed(range(n-1)):
    r[i] = gcd(r[i+1], a[i+1])
# print(r)

# a[i]を除いた最大公約数を計算
ans = 0
for i in range(n):
    ans = max(ans, gcd(l[i],r[i]))

# 出力
print(ans)
### BUGGY CODE ###

t = input()

if t[0] == "?":
    t = "D" + t[1:]

for i in range(1,len(t)):
    if t[i] == "?":
        t = t[:i] + "D" + t[i+1:]
print(t)


### FIXED CODE ###

t = input()
print(t.replace("?", "D"))

# if t[0] == "?":
#     t = "D" + t[1:]

# for i in range(1,len(t)):
#     if t[i] == "?":
#         t = t[:i] + "D" + t[i+1:]
### BUGGY CODE ###

n , q = map(int, input().split())

tree = {}
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a] = tree.get(a, []) + [b]

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root, reaf in tree.items():
    for i in reaf:
        op[i] += op[root]

print(*op[1:])


### FIXED CODE ###

n , q = map(int, input().split())

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

op = [0] * (n+1)
for i in range(q):
    p, x = map(int, input().split())
    op[p] += x

for root, reaf in enumerate(tree):
    for i in reaf:
        op[i] += op[root]

print(*op[1:])
### BUGGY CODE ###

N=int(input())
hako=list(map(int,input().split()))
tasu=0
fin=0
for i in range(N):
  for k in range(N-i-1):
    tasu=tasu+hako[i+k+1]
  fin=fin+hako[i]*tasu
  tasu=0
fin=fin%(10**9+7)
print(fin)

### FIXED CODE ###

N=int(input())
hako=list(map(int,input().split()))
tasu=sum(hako)
tasu=tasu**2
for i in range(N):
  tasu=tasu-(hako[i])**2
tasu=tasu//2
tasu=tasu%(10**9+7)
print(tasu)
### BUGGY CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = []
max_p = 0
for i in range(N):
  Es.append((ps[i]+1)/2)
  if i<(K-1):
    continue
  elif i==(K-1):
    max_p = sum(Es)
  else:
    Es.pop(0)
    p = sum(Es)
    if max_p < p:
      max_p = p
print(max_p)

### FIXED CODE ###

N, K = map(int, input().split())
ps = list(map(int, input().split()))
Es = [(ps[i]+1)/2 for i in range(N)]
maxs = []
for i in range(1, N+1):
  if i<K:
    continue
  elif i==K:
    tmp = sum(Es[:i])
    maxs.append(tmp)
  else:
    tmp = tmp +Es[i-1]-Es[i-K-1]
    maxs.append(tmp)
print(max(maxs))
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort(reverse=True)
#print(lst)
set_lst = set(lst)

if lst[n - 1] == 1:
  if n > 1:
    if lst[n - 1] == lst[n - 2]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  count = 0
  for i in range(n):
    if i < n - 1:
      flag = True
      if (lst[i] == lst[i + 1]) or (lst[i] == lst[i - 1] and i > 0):
        flag = False
      else:
        for j in set_lst:
          if j >= lst[i]:
            continue
          if lst[i] % j == 0:
            flag = False
            break
      if flag:
        count += 1
    if i == n - 1:
      if n > 1:
        if lst[i] != lst[i - 1]:
          count += 1
      else:
        count += 1
  print(count)

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = 1+P
    kitaichi.append(kitai)
ans = []
for j in range((n-k)+1):
    a = sum(kitaichi[j:j+k])
    ans.append(a)
ans.sort(reverse=True)

print(ans[0]/2)


### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
kitaichi = []
for i in range(n):
    P = p[i]
    kitai = 1+P
    kitaichi.append(kitai)
m = [0,]
a = 0
for j in range(n):
    a += kitaichi[j]
    m.append(a)
ans = 0
for l in range(n-k+1):
    temp = m[l+k]-m[l]
    if temp> ans:
      ans = temp
print(ans/2)
### BUGGY CODE ###

def main():
    from itertools import product

    n, s = int(input()), input()
    ans = 0

    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            if s[i] == s[j]:
                continue
            t = {'R', 'G', 'B'} - {s[i], s[j]}
            t = t.pop()
            d = j - i
            ans += s[j + 1:].count(t)
            if j + d < n and s[j + d] == t:
                ans -= 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, s = int(input()), input()
    r, g, b = s.count('R'), s.count('G'), s.count('B')
    ans = r * g * b
    v = {'R', 'G', 'B'}
    for i in range(n - 2):
        for j in range(n // 2 + 1):
            if i + j + j < n:
                if v == {s[i], s[i + j], s[i + j + j]}:
                    ans -= 1
    print(ans)


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

n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[inf for i in range(num_v)] for j in range(num_v)]
    for e in edge: cost[e[0]][e[1]] = e[2]
    used = [False for i in range(num_v)]
    d = [inf for j in range(num_v)]

    d[start] = 0;
    while True:
        v = -1
        for u in range(num_v):
            if (not used[u]) and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1: break
        used[v] = True
        for x in range(num_v):
            d[x] = d[x] if d[x] < d[v] + cost[v][x] else d[v] + cost[v][x]
    return d

from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

### FIXED CODE ###

import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    su.append([x1-1,y1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
 
 
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])
### BUGGY CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

#!/usr/bin/env python3

import itertools

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

max_x = max(max(x_list), A)
dp = [[[0 for s in range(N * max_x + 1)] for k in range(N + 1)] for j in range(N + 1)]
dp[0][0][0] = 1
ka_list = []

for j in range(N + 1):  # 何番目の数か
    x = x_list[j - 1]
    for k in range(N + 1):  # k枚選ぶとき
        for s in range(N * max_x + 1):
            if j == 0 and k == 0 and s == 0:
                dp[0][0][0] = 1
            elif j >= 1 and s < x:
                # オーバーするので選べない
                # ひとつ前と同じになる
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x]
            else:
                dp[j][k][s] = 0

ans = sum([dp[N][k][k * A] for k in range(1, N + 1)])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

import itertools

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

max_x = max(max(x_list), A)
dp = [[[0 for s in range(N * max_x + 1)] for k in range(N + 1)] for j in range(N + 1)]
dp[0][0][0] = 1
ka_list = []

for j in range(N + 1):  # 何番目の数か
    x = x_list[j - 1]
    for k in range(N + 1):  # k枚選ぶとき
        for s in range(N * max_x + 1):
            if j == 0 and k == 0 and s == 0:
                dp[0][0][0] = 1
            elif j >= 1 and s < x:
                # オーバーするので選べない
                # ひとつ前と同じになる
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x]
            else:
                dp[j][k][s] = 0

ans = sum([dp[N][k][k * A] for k in range(1, N + 1)])
print(ans)
### BUGGY CODE ###

S=input()
Q=int(input())
sousa=[list(map(str,input().split())) for i in range(Q)]
counter=0
up=''
down=''
for i in sousa:
    if i[0]=='1':
#         S=S[::-1]
        counter+=1
    if i[0]=='2':
        if counter%2==0:
            if i[1]=='1':
                up=i[2]+up
            if i[1]=='2':
                down=down+i[2]
        else:
            if i[1]=='1':
                down=down+i[2]
            if i[1]=='2':
                up=i[2]+up   
                
S=up+S+down
if counter%2==1:
    S=S[::-1]

print(S)

### FIXED CODE ###

S=input()
Q=int(input())
sousa=[list(map(str,input().split())) for i in range(Q)]
counter=0
up=''
down=''
for i in sousa:
    if i[0]=='1':
#         S=S[::-1]
        counter+=1
    if i[0]=='2':
        if counter%2==0:
            if i[1]=='1':
                up=i[2]+up
            if i[1]=='2':
                down=down+i[2]
        else:
            if i[1]=='1':
                down=down+i[2]
            if i[1]=='2':
                up=i[2]+up   
                
S=up+S+down
if counter%2==1:
    S=S[::-1]

print(S)
### BUGGY CODE ###

a, b, x = map(int, input().split())
d=0

for num in range(a,b+1):
    if num%x==0:
        d=d+1
    else:
        pass
print(d)

### FIXED CODE ###

a, b, x = map(int, input().split())
d=b//x-a//x
if a%x==0:
    d=d+1
    print(d)
else:
    print(d)
### BUGGY CODE ###

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


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))
    

    # queue = [ [ -length of the log cut  , the initial length of log , the number of cut ] ]
    hq = [ [-a,a,0] for a in A_list ]
    heapq.heapify(hq)

    while K:
        _ , len_a, num_cut = heapq.heappop(hq)
        num_cut += 1
        K -= 1

        heapq.heappush(hq, [ -(len_a / (num_cut + 1)) , len_a , num_cut] )
    
    
    len_cut , len_a, num_cut = heapq.heappop(hq)
    len_cut = -(len_cut // 1)  # round up (len_cut is negative number)
    print( int(len_cut) )


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from decimal import Decimal, ROUND_HALF_UP


def main():
    N,K = list(map(int, sys.stdin.readline().split()))
    A_list = list(map(int, sys.stdin.readline().split()))


    def check(length :int) -> bool:
        cnt = 0

        for a in A_list:
            if a >= length:
                quotient = a / length
                divide = -(-quotient // 1)  # round up
                cnt += (divide - 1)
        
        return (True if cnt <= K else False)


    L = 0.1            # the minimum length
    R = max(A_list)  # the maximum length

    while (R - L) > 0.01:
        M = L + (R - L) / 2

        if check(M):
            R = M
        else:
            L = M
    
    
    ans = float( Decimal(str(M)).quantize(Decimal('1E-1'), rounding=ROUND_HALF_UP) )
    ans = -(-ans // 1)  # round up
    print( int(ans) )


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

# ABC123
cnd = list(map(int, [input().rstrip() for _ in range(6)]))
n = cnd[0]
arr = [n] + [0] * 6
ans = 0
while arr[5] != n:
    for i in range(5, 0, -1):
        if arr[i - 1] == 0:
            continue
        move = min(arr[i - 1], cnd[i])
        arr[i] += move
        arr[i - 1] -= move
    ans += 1
print(ans)

### FIXED CODE ###

# ABC123C - Five Transportations
from math import ceil
cnd = list(map(int, [input().rstrip() for _ in range(6)]))
print(ceil(cnd[0] / min(cnd[1:])) + 4)
### BUGGY CODE ###

k,s = map(int,input().split())
f = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                f+=1
print(f)

### FIXED CODE ###

k,s = map(int,input().split())
f = 0
for i in range(k+1):
    for j in range(k+1):
        l = s-i-j
        if 0 <= l <=k:
            f+=1
print(f)
### BUGGY CODE ###

k = int(input())

if k%2==0:#偶数時の処理
  print(-1)
  exit()

flg = False
for i in range(1,10**6):
  s = '7'*i
  s = int(s)
  if s%k==0:
    flg = True
    break
    
print(i if flg else '-1')

### FIXED CODE ###

k = int(input())
x = 7%k

flg = False
for i in range(1,k+1):
  x = x%k
  if x ==0:
    flg = True
    break
  else:
    x = x*10+7
  
print(i if flg else '-1')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*(N)

for i in range(1,N):
    now = h[i]
    dp[i] = min([abs(now-h[j])+dp[j] for j in range(max(i-K,0),i)])

print(dp[N-1])
### BUGGY CODE ###

A, B, K = input().split(' ')
A = int(A)
B = int(B)
K = int(K)
N = []
for i in range(A, B+1):
  if i < A + K:
    print(i)
  elif i > B-K:
    print(i)

### FIXED CODE ###

A, B, K = input().split(' ')
A = int(A)
B = int(B)
K = int(K)
N = []
if B-A>K:
  for i in range(A, A+K):
    print(i)
    N.append(i)
  for i in range(B-K+1, B+1):
    if not i in N:
      print(i)

else:
  for i in range(A, B+1):
    if i < A + K:
      print(i)
    elif i > B-K:
      print(i)
### BUGGY CODE ###

from collections import deque
def gridbfs(grid):
    INF = 10**18

    gridy = len(grid)
    gridx = len(grid[0])

    dist = [[INF]*gridx for _ in range(gridy)]
    q = deque()
    for y in range(gridy):
        for x in range(gridx):
            if grid[y][x] == '#':
                dist[y][x] = 0
                q.append((y,x))

    while q:
        y,x = q.popleft()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            ny,nx = y+dy, x+dx
            if not (0 <= ny < gridy and 0 <= nx < gridx):
                continue
            if dist[ny][nx] != INF:
                continue
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

    return dist

H,W = map(int,input().split())
Grid = [input() for _ in range(H)]
d = gridbfs(Grid)
print(max(max(d[i]) for i in range(H)))


### FIXED CODE ###

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

q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append((i, j))
ans = -1

while len(q) != 0:
    ans += 1
    qq = []
    while len(q) != 0:
        t = q.popleft()
        i,j = t[0],t[1]
        if i > 0 and A[i-1][j] == '.':
            qq.append((i-1,j))
            A[i-1][j] = '#'
        if j > 0 and A[i][j-1] == '.':
            qq.append((i,j-1))
            A[i][j-1] = '#'
        if i < H-1 and A[i+1][j] == '.':
            qq.append((i+1,j))
            A[i+1][j] = '#'
        if j < W-1 and A[i][j+1] == '.':
            qq.append((i,j+1))
            A[i][j+1] = '#'
    q = deque(qq)

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

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

for i in range(K):
  new = [0] * (N+1)
  for j in range(N):
    new[max(0, j-A[j])] += 1
    if j+A[j]+1 <= N-1:
      new[j+A[j]+1] -= 1
  A[0] = new[0]
  for j in range(1, N):
    new[j] += new[j-1]
    A[j] = new[j] 
  for ai in A:
    if ai != N:
      break
  else:
    break
    
print(' '.join([str(ai) for ai in A]))


### FIXED CODE ###

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

for i in range(K):
  new = [0] * (N+1)
  for j in range(N):
    new[max(0, j-A[j])] += 1
    if j+A[j]+1 <= N-1:
      new[j+A[j]+1] -= 1
  A[0] = new[0]
  for j in range(1, N):
    new[j] += new[j-1]
    A[j] = new[j] 
  for ai in A:
    if ai != N:
      break
  else:
    break
    
print(' '.join([str(ai) for ai in A]))