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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9 + 7

def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

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

euler = []
def dfs(pre,now):
    euler.append(now)
    for to in G[now]:
        if to == pre:
            continue
        dfs(now,to)
    euler.append(pre)

dfs(-1,0)

data = [[] for i in range(n)]
last = [-1]*n
for i,x in enumerate(euler[:-1]):
    if last[x] == -1:
        last[x] = i
        continue
    data[x].append((i-last[x])//2)
    last[x] = i

for i in range(n):
    if sum(data[i]) == n-1:
        continue
    data[i].append(n-1-sum(data[i]))

two = [1]
now = 1
for i in range(n):
    now *= 2
    now %= mod
    two.append(now)

ans = 0
for i in range(n):
    now = 1
    for x in data[i]:
        now += two[x]-1
        now %= mod
    ans += two[n-1]-now
    ans %= mod


ans *= pow(two[n],mod-2,mod)
ans %= mod

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

d_to_i = [[] for _ in range(n)]

for i in range(n):
    d_to_i[depth[i]].append(i)

data = [[] for _ in range(n)]

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)
### BUGGY CODE ###

def LI(): return list(map(int,input().split()))
N,Q = LI()
ab = [LI() for _ in range(N-1)]
px = [LI() for _ in range(Q)]
ans = [0]*(N+1) #1_indexed
graph = [[] for _ in range(N+1)] #1_indexed
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [-1]*(N+1) #1_indexed
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for g_NO in graph[s]:
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])

### FIXED CODE ###

import collections,copy,sys
def LI(): return list(map(int,sys.stdin.readline().split()))
N,Q = LI()
ans = [0]*(N+1)
graph = [collections.deque() for _ in range(N+1)] #1_index
for _ in range(N-1):
    a,b = LI()
    graph[a].append(b)
    graph[b].append(a)
for _ in range(Q):
    p,x = LI()
    ans[p] += x
seen = [-1]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]!=-1:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
### BUGGY CODE ###

import re

i = int(input().split()[1])
s = input()
k = 0
result = []

while k < i:
    ft, et = map(int, input().split())
    result.append(s[ft - 1:et].count("AC"))
    #result.append(len(re.findall("AC", s[ft - 1:et])))
    k += 1

for kekka in result:
    print(kekka)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
s = input()

count = [0]
for i in range(1, n):
    count.append(count[i-1])
    if(s[i-1:i+1] == "AC"):
        count[i] += 1

# print(count)

for _ in range(q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

## ABC 072 c
n = int(input())
a = [int(i) for i in input().split()]
a.sort()

cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = a.count(x)+a.count(x-1)+a.count(x+1)
    cnt = max(c,cnt)

print(cnt)


### FIXED CODE ###

## ABC 072 c
from collections import Counter

n = int(input())
a = [int(i) for i in input().split()]
a.sort()

ad = Counter(a)
cnt = 0
for x in range(a[0]-1, a[-1]+2):
    c = ad[x]+ad[x-1]+ad[x+1]
    cnt = max(c,cnt)

print(cnt)
### BUGGY CODE ###

def inpl(): return [int(i) for i in input().split()]
def next(v):
    for i in edge[v].copy():
        if i in path:
            continue
        if i in path1:
            continue
        return i
    return -1

from collections import defaultdict
edge = defaultdict(lambda: [])
N, M = inpl()
for _ in range(M):
    A,B = inpl()
    edge[A].append(B)
    edge[B].append(A)
v = 1
nv = 1
path = [1]
path1 = [1]
while nv >= 0:
    nv = next(v)
    path.append(nv)
    v = nv
path.pop()
v = 1
nv = 1
while nv >= 0:
    nv = next(v)
    path1.append(nv)
    v = nv
path1=list(reversed(path1))
path1.pop(0)
path1.pop()
path = path1 + path
print(len(path))

print(*path)

### FIXED CODE ###

def inpl(): return [int(i) for i in input().split()]
def next(v):
    for i in edge[v]:
        if visited[i]:
            continue
        visited[i] = True
        return i
    return -1

from collections import defaultdict
edge = defaultdict(lambda: [])
N, M = inpl()
visited = [False for _ in range(N+1)]
visited[1] = True
for _ in range(M):
    A,B = inpl()
    edge[A].append(B)
    edge[B].append(A)
v = 1
nv = 1
path = [1]
while nv >= 0:
    nv = next(v)
    path.append(nv)
    v = nv
path.pop()
path = list(reversed(path))
v = 1
nv = 1
while nv >= 0:
    nv = next(v)
    path.append(nv)
    v = nv
path.pop()
print(len(path))
print(*path)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict,Counter

s = ns()
d = defaultdict(int)
d[0] += 1
k = 0
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*(10**k)
    n%=2019
    d[n] += 1
    k+=1

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

from collections import defaultdict

s = ns()
d = defaultdict(int)
d[0] += 1
k = 1
n = 0
for i in range(len(s))[::-1]:
    n += int(s[i])*k%2019
    n%=2019
    d[n] += 1
    k = (k*10)%2019

ans = 0

for j in d.values():
    if j > 1:
        ans += j*(j-1)//2

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

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [100000000000 for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(min(i+1,k+1)):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [100000000000 for _ in range(n)]
dp[0] = 0
for i in range(n):
    for j in range(min(i,k)+1):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])
### BUGGY CODE ###

from collections import deque
S=input()
Q=int(input())

ans=deque()
for s in S:
    ans.append(s)
rev=False

for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            ans.appendleft(query[2])
        else:
            ans.append(query[2])
    # print(ans)
if not rev:
    for i in range(len(ans)):
        print(ans[i],end="")
else:
    for i in range(len(ans)-1,-1,-1):
        print(ans[i],end="")

### FIXED CODE ###

S=input()
Q=int(input())

# deq=deque()
# for s in S:
#     deq.append(s)

rev=False
front=""
last=""
# ans+=S

for _ in range(Q):
    query=input().split()
    if query[0]=="1":
        rev = not rev
        # print(rev)
    else:
        if rev:
            query[1]=str(3-int(query[1]))
        if query[1]=="1":
            # deq.appendleft(query[2])
            front=query[2]+front
        else:
            # deq.append(query[2])
            last+=query[2]

# if rev:
#     deq.reverse()
# # ans=""
# for i in range(len(deq)):
#     ans+=deq[i]

if not rev:
    print(front+S+last)
else:
    print(last[::-1]+S[::-1]+front[::-1])
### BUGGY CODE ###

A, B, K = map(int, input().split())
if A + B == K:
  print("0 0")
  exit()
while True:
  if A >= K:
    t1 = K
    K -= K
    A -= t1
  elif A > 0:
    A -= 1
    K -= 1
  elif B >= K:
    t2 = K
    K -= K
    B -= t2
  elif B > 0:
    B -= 1
    K -= 1
  if K == 0:
    break
print(str(A) + " " + str(B))

### FIXED CODE ###

A, B, K = map(int, input().split())
if A >= K:
  print(A - K, B)
elif B >= (K - A):
  print(0, B - (K - A))
else:
  print(0, 0)
### BUGGY CODE ###

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

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

t.sort(reverse=True)

memo = []

for i in range(m):
    if len(memo) == 0:
        x=t.pop(0)
    elif len(t) == 0:
        x=memo.pop(0)
    elif t[0] >= memo[0]:
        x=t.pop(0)
    else:
        x=memo.pop(0)
    x = int(x/2)
    memo.append(x)
    #print(t)
print(sum(t)+sum(memo))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())

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

for i in range(n):
    t[i] = -t[i]

t.sort()

for i in range(m):
    x=heapq.heappop(t)
    x = -x
    x = int(x/2)
    heapq.heappush(t,-x)
    #print(t)
print(-sum(t))
### BUGGY CODE ###

import sys
input()
ls = []
line = map(lambda x:x.split(), sys.stdin.readlines())
for i in line:
    if i[0] == "insert":
        ls.append(i[1])
    else:
        print("yes" if i[1] in ls else "no")

### FIXED CODE ###

dic = {}
line = []
for i in range(int(input())):
    line.append(input().split())
for i in line:
    if i[0][0] == "i":
        dic[i[1]] = None
    else:
        print("yes" if i[1] in dic else "no")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N =  int(input())
    E = [[] for _ in range(N+1)]
    D = {}
    L = [-1 for _ in range(N)]
    for i in range(1,N):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
        D[(a,b)] = D[(b,a)] = i
    r = 1
    l = len(E[1])
    for i in range(2,N+1):
        k = len(E[i])
        if l < k:
            r, l = i, k
    d = l
    q = [(r,0)]
    z = []
    while q:
        v, c = q.pop()
        C = list(range(1,d+1))
        for u in E[v]:
            if L[D[(v,u)]] == -1:
                x = C.pop()
                if c == x:
                    x = C.pop()
                q.append((u,x))
                L[D[(v,u)]] = x
                z.append(u)
    L[0] = d
    res = '\n'.join(map(str, L))
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N =  int(input())
    E = [[] for _ in range(N+1)]
    D = {}
    L = [-1 for _ in range(N)]
    for i in range(1,N):
        a, b = map(int, input().split())
        E[a].append(b)
        E[b].append(a)
        D[(a,b)] = i
    r = 1
    q = [(r,0)]
    d = 0
    while q:
        v, c = q.pop()
        d = max(d, len(E[v]))
        C = 0
        for u in E[v]:
            if L[D.get((v,u), D.get((u,v),-1))] == -1:
                C += 1
                x = C
                if c == x:
                    C += 1
                    x = C
                q.append((u,x))
                L[D.get((v,u), D.get((u,v),-1))] = x
    L[0] = d
    res = '\n'.join(map(str, L))
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]
dp = [[None]*(w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
for i in range(1, n+1):
    wi, vi = wv[i-1]
    di = dp[i]
    dio = dp[i-1]
    for j in range(wi):
        di[j] = dio[j]
    for j in range(wi, w+1):
        di[j] = max(dio[j], dio[j-wi]+vi)
print(dp[-1][-1])

### FIXED CODE ###

def main():
    n, w = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [[None]*(w+1) for _ in range(n+1)]
    dp[0] = [0]*(w+1)
    for i in range(1, n+1):
        wi, vi = wv[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(wi):
            di[j] = dio[j]
        for j in range(wi, w+1):
            di[j] = max(dio[j], dio[j-wi]+vi)
    print(dp[-1][-1])

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

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(N):
    print(max(A[:i]+A[i+1:]))



### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]

max_num = max(A)
a = sorted(A)
second = a[-2]

for i in range(N):
    if A[i] == max_num:
        print(second)
    else:
        print(max_num)
### BUGGY CODE ###

a,b=map(int,input().split())
c=[]
for i in range(a,b+1):
  for j in range(a,b+1):
    if i<j:
        c.append((i*j)%2019)
print(min(set(c)))


### FIXED CODE ###

a,b=map(int,input().split())
if b-a>=2019:
    print(0)
    exit()
d=[]
for i in range(a,b+1):
    if i%2019==0:
        print(0)
        exit()
    for j in range(a,b+1):
        if i<j:
            d.append((i*j)%2019)
print(min(d))
### BUGGY CODE ###

def main():
    N = int(input())
    power = 1
    for i in range(N):
        power *= (i + 1)
    print(power%(1000000000 + 7))
main()

### FIXED CODE ###

import math
def main():
    N = int(input())
    power = math.factorial(N)
    print(power%(1000000000 + 7))
main()
### BUGGY CODE ###

import numpy as np
n,*a=map(int,open(0).read().split())
a=np.array(sorted(a))
i = 0
while len(a):
    try:
        if a[0] != a[1]:
            i+=1
    except:
      i+=1
    a = a[a%a[0] != 0]
print(i)

### FIXED CODE ###

_,*a = map(int, open(0).read().split())
a.sort()
m = -~a[-1]
c = [0]*m
for i in a:
    c[i] += 1
    if c[i] > 1:
        continue
    for j in range(i * 2, m, i):
        c[j] = 2
print(sum(c[i]==1for i in a))
### BUGGY CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y)%prime, an ,0 )

print(ans)

### FIXED CODE ###


import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

print(ans%prime)
### BUGGY CODE ###

import bisect
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()

for j in range(m):
    b=a[-1]
    a.pop()
    bisect.insort(a,b/2)
print(sum( int( i//1) for i in a ))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    b=-heapq.heappop(a)
    heapq.heappush(a,-b/2)
print(int( sum(-i//1 for i in a)) )
### BUGGY CODE ###

s=input()
count_1=0
num =int(input())


for x in range(num):
    i=input().rstrip().split()
    if i[0]=="1":
        count_1+=1
        
    elif i[1]=="1" and count_1%2==0:
        s=i[2]+s
   
    elif i[1]=="1" and count_1%2==1:
        s=s+i[2]

    elif i[1]=="2" and count_1%2==0:
        s=s+i[2]

    elif i[1]=="2" and count_1%2==1:
        s=i[2]+s

if count_1%2==1:
    s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
s1=""
s2=""
count_1=0
l=[]
num =int(input())
 
 
for x in range(num):
    i=input().rstrip().split()
    if i[0]=="1":
        count_1+=1
        
    elif i[1]=="1" and count_1%2==0:
        s1=i[2]+s1
   
    elif i[1]=="1" and count_1%2==1:
        s2=s2+i[2]
 
    elif i[1]=="2" and count_1%2==0:
        s2=s2+i[2]
 
    elif i[1]=="2" and count_1%2==1:
        s1=i[2]+s1
s=s1+s+s2
 
if count_1%2==1:
    s=s[::-1]
print(s)
### BUGGY CODE ###

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

import sys
args = sys.argv

debug_flg = False
def debug(val1,val2="",val3="",val4=""):
    global debug_flg
    if debug_flg:
        print(val1,val2,val3,val4,sep=" , ")

if len(args) != 2:
    n= int(input())
    s= input()
else:
    debug_flg = True
    if args[1] == "2":
        n=39
        s="RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"
    elif args[1] == "3":
        n=1
        s="R"
    else:
        n=4
        s="RRGB"

snum = []
for i in range(1,n+1):
    if s[i-1] == "R":
        snum.append(0)
    elif s[i-1] == "G":
        snum.append(1)
    elif s[i-1] == "B":
        snum.append(2)

ret =0
for i in range(1,n-1):
    for j in range(i,n):
        if snum[i-1] == snum[j-1]:
            continue
        for k in range(j,n+1):
            if j-i == k-j:
                continue
            if snum[i-1] == snum[k-1]:
                continue
            if snum[j-1] == snum[k-1]:
                continue
            ret += 1

print(ret)






### FIXED CODE ###

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

    r = s.count("R")
    g = s.count("G")
    b = s.count("B")

    ans = r * g * b
    snum = tuple(s[:])
    for i in range(1,n-1):
        for j in range(i,n):
            k = j * 2 - i
            if k > n:
                break

            if snum[i-1] != snum[j-1] and snum[i-1] != snum[k-1] and snum[j-1] != snum[k-1]:
                ans -= 1

    print(ans)


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

N = int(input())
A = list(input())
R = []
B = []
G = []
for i in range(N):
  if A[i] == "R":
    R.append(i)
  elif A[i] == "G":
    G.append(i)
  else:
    B.append(i)
ans = 0
for i in range(len(R)):
  for j in range(len(G)):
    for k in range(len(B)):
      if (max(R[i], G[j], B[k]) + min(R[i], G[j], B[k]))/2 != (R[i]+G[j]+B[k])/3:
        ans += 1
print(ans)
        


    

### FIXED CODE ###

N = int(input())
A = list(input())
ans = A.count("R")*A.count("G")*A.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2*j-i
    if k<N and A[k] != A[i] and A[k] != A[j] and A[i] != A[j]:
      ans -= 1
print(ans)
### BUGGY CODE ###

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

def z_algorithm(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    tmp = 0
    for a in A:
        if 2 * a > N:
            continue
        else:
            tmp = max(tmp, a)
    return tmp

ans = 0
for i in range(N):
    ans = max(ans, z_algorithm(S[i:]))

print (ans)

### FIXED CODE ###

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

def z_algorithm(S):
    N = len(S)
    A = [0] * N
    i = 1
    j = 0
    A[0] = l = len(S)
    while i < l:
        while i + j < l and S[j] == S[i + j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l - i > k < j - A[k]:
            A[i + k] = A[k]
            k += 1
        i += k
        j -= k
    tmp = 0
    for index, a in enumerate(A):
        if a <= index:
            tmp = max(tmp, a)
    # print (A)
    return tmp

ans = 0
for i in range(N):
    ans = max(ans, z_algorithm(S[i:]))

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

#/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict
import copy

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = set() 
cover = set()
grid = defaultdict(lambda:None)
rowGrid = defaultdict(set)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].add(c)
	grid[(r, c)] = a 
	rowIdx.add(r)

pairIdx = copy.copy(rowIdx)	
for i in rowIdx:
	tempRow = rowGrid[i]
	tempRow.difference_update(cover)
	if (len(tempRow) is 0):
		continue
	pairIdx.remove(i)
	for j in pairIdx:
		tempPair = rowGrid[j]
		mark = 1
		for k in tempRow:
			if (grid[(j, k)] != None):
				diff = grid[(i, k)] - grid[(j, k)]
				mark = 0 
		if (mark is 1):
			continue
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP is None and anchor < diff):
				print('No')
				exit()
			elif (anchorP is not None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP is None and anchor < -diff):
				print('No')
				exit()
	cover &= tempRow
	if (len(cover) is C):
		break
print('Yes')

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

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

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

maxval = 0

def expectedval(inp):
	return (1 + inp) * (inp/2) / inp


for i in range(n-(k-1)):
	summ = 0
	for j in range (k):
		summ += expectedval(plist[i + j])
	maxval = max(summ, maxval)

print(maxval)



### FIXED CODE ###

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

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

maxval = 0

temp = -1

def expectedval(inp):
	return (1 + inp) /2

for i in range(n-(k-1)):
	# print(i, k)
	summ = 0
	if temp == -1:
		for j in range (k):
			summ += expectedval(plist[i + j])
		temp = summ
	else:
		# print(plist[i-1], plist[i+k -1], expectedval(plist[i - 1]), expectedval(plist[i + k - 1]))
		summ = temp - expectedval(plist[i - 1]) + expectedval(plist[i + k - 1])
		temp = summ
	# print(summ)
	maxval = max(summ, maxval)

print(maxval)
### BUGGY CODE ###

def main():
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  n,k = map(int,readline().split())
  h = list(map(int,readline().split()))

  dp = [float('inf')]*n
  dp[0] = 0

  for i in range(1,n):
    for j in range(min(k,i)):
      dp[i] = min(dp[i], dp[i-1-j]+abs(h[i]-h[i-1-j]))

  print(dp[n-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
h = list(map(int,readline().split()))

dp = [float('inf')]*n
dp[0] = 0

for i in range(1,n):
  for j in range(min(k,i)):
    dp[i] = min(dp[i], dp[i-1-j]+abs(h[i]-h[i-1-j]))

print(dp[n-1])