Harryxun/stf_run huggingface dataset:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    graph[u].add((v,w))
    graph[v].add((u,w))

res = [0 for i in range(N)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    new_nodes = graph[node]
    # print(index_num)
    for new_node,w in new_nodes:
        if new_node == p:
            continue
        if w% 2 == 1:dfs(new_node,node,1-color)
        else:dfs(new_node,node,color)

#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

# print(res[1:])
for i in range(N):
    print(res[i])


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys



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

N = int(input())
graph = [set() for i in range(N+1)]

for i in range(N-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w = w % 2
    graph[u].add((v,w))
    graph[v].add((u,w))


res = [None for i in range(N+1)]

# v は今見ている頂点，p はｖの親
def dfs(node,p,color): # Depth First Serch
    res[node] = color
    for new_node,w in graph[node]:
        if new_node == p:
            pass
        else:
            if w == 1:dfs(new_node,node,1-color)
            else:dfs(new_node,node,color)
#tree 探索　
# vは頂点，ｐは親
dfs(0,-1,0)

for i in range(N):
    print(res[i])
n=int(input())
arr=list(map(int,input().split()))
s=0
d={}
for i in arr:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
    s+=i
for i in range(int(input())):
    a,b=map(int,input().split())
    if a in d:
        s=s-a*d[a]+b*d[a]
    if b in d:
        d[b]+=d[a]
    else:
        if a in d:
            d[b]=d[a]
    d[a] = 0
    print(s)


### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
s=0
d={}
for i in arr:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
    s+=i
for i in range(int(input())):
    a,b=map(int,input().split())
    if a in d:
        s=s-a*d[a]+b*d[a]
    if b in d and a in d:
        d[b]+=d[a]
    else:
        if a in d:
            d[b]=d[a]
    d[a] = 0
    print(s)
a,b,c,d = map(int,input().split())

while True:
if a>0 and c>0:
    c -= b
    if a>0 and c>0:
      a -= d
      
else:
  break
  
if a>c:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c,d = map(int,input().split())
 
while a>0 and c>0:
  if c>0:
    c += -b
    
  if c<=0:
    print("Yes")
    break
    
    
  if a>0:
    a += -d
    
  if a<=0:
    print("No")
    break
import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


idx=0
while i==len(nxt):
    i=nxt[idx]
    i+=1
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1<<20)
h,w=[int(x) for x in input().split()]
ch,cw=[int(x) for x in input().split()]
dh,dw=[int(x) for x in input().split()]
ch-=1
cw-=1
dh-=1
dw-=1

s=[]
for _ in range(h):
    s.append(list(input()))

nxt=[[ch,cw,0]]
#再起
def rcl(y,x,now):
    
    if y==dh and x==dw:
        print(now)
        exit()
    
    if s[y][x]=='#':
        return
    
    s[y][x]='#'
    # 四方を見る
    for i in range(4):
        yy,xx=-1,0
        if i==1:yy,xx=0,1
        if i==2:yy,xx=1,0
        if i==3:yy,xx=0,-1
        
        if y+yy<0 or h<=y+yy or x+xx<0 or w<=x+xx:
            continue
        if s[y+yy][x+xx]=='#':
            continue
        
        rcl(y+yy,x+xx,now)
    #5*5
    for i in range(-2,3):
        for j in range(-2,3):
            if i==0 and j==0:
                continue
            if y+i<0 or h<=y+i or x+j<0 or w<=x+j:
                continue
            if s[y+i][x+j]=='.':
                nxt.append([y+i,x+j,now+1])
                s[y+i][x+j]=now+1


while nxt:
    i=nxt.pop(0)
    if i[0]==dh and i[1]==dw:
        print(i[2])
        exit()
    rcl(i[0],i[1],i[2])
print(-1)
n=int(input())
t=list(map(int,input.split()))
m=int(input())
for i in range(m):
    p,x=map(int,input().split())
    s=0
    for j in range(len(t)):
        if j==p-1:
            s+=x
        else:
            s+=t[j]
    print(s)  
        
    


### FIXED CODE ###

n=int(input())
t=list(map(int,input().split()))
m=int(input())
for i in range(m):
    p,x=map(int,input().split())
    s=0
    for j in range(len(t)):
        if j==p-1:
            s+=x
        else:
            s+=t[j]
    print(s)
from sys import stdin
n = int(stdin.readline().rstrip())
l = [int(x) for x in stdin.readline().rstrip().split()]
max = max(l)
sum = sum(l, -1*max)
print("Yes") if sum > max else print("No")

### FIXED CODE ###

from sys import stdin
a, b = [int(x) for x in stdin.readline().rstrip().split()]
print(a/b)
N = int(input())
def prime_dict(n):
    a = {}
    if n%2 == 0:
        a[2] = 1
        n//=2
        exp2 = 2
    while n%(2**exp2) == 0 and (n >= 2**exp2):
        a[2] += 1
        n //= 2**exp2
        exp2 += 1
    while n%2 == 0:
        n //= 2
    f = 3
    expn = 1
    while f**expn <= n:
        while f**expn <= n:
            if n%(f**expn) == 0:
                if f not in a:
                    a[f] = 1
                else:
                    a[f] += 1
                n //= f**expn
            expn += 1
        while n%f == 0:
            n //= f
        f += 2
        expn = 1
    if n!= 1:
        a[n] = 1
    return a

primes = prime_dict(N)
ans = sum(primes.values())
print(ans)



### FIXED CODE ###

from collections import Counter
N = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 0
primes = prime_factorize(N)
pc = Counter(primes)
for v in pc.values():
    now = 1
    while now*(now+1)//2 <= v:
        now += 1
    ans += now-1
print(ans)
n=int(input())
s=list(input())

def res():
    ct=0
    for i in range(n):
        if i+2 > n:
            return ct
        if s[i] =="A"and s[i+1]=="B" and s[i+2]=="C":
            ct+=1

print(res())

### FIXED CODE ###

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

def res():
    ct=0
    for i in range(n):
        if i+2 > n-1:
            return ct
        if s[i] =="A"and s[i+1]=="B" and s[i+2]=="C":
            ct+=1

print(res())
n = int(input())
k = int(nput())
price = []
cost = 0
for p in range(n + 1):
        p = int(input())
        price.append(p)

price.sort()
for  p in price:
        cost += p

print(price)

### FIXED CODE ###

n, k,  =map(int, input().split())
cost = 0
price = list(map(int, input().split()))
        
price.sort()
del price[k:]
for p in price:
        cost += p

print(cost)
L,N=(int(i) for i in input().split())
n = int(input())
X = []
for i in range(0,N):
    a = int(input())
    X.append(a)
import math
result=0
if X[math.ceil(N/2)]<L/2:
  for i in range (1,N/2):
    for j in range (N,L/2,-1):
      result+=abs(X[j]-X[i])
else:
   for i in range (1,N/2):
    for j in range (N,N/2,-1):
      result+=abs(X[i]-X[j])
print(result)

### FIXED CODE ###

a,b,c=(int(i) for i in input().split())
if b+1>=c:
  print(b+c)
else:
  if a+1>=c-b:
    print(b+c)
  else:
    print(2*b+a+1)
import math
#数値ひとつ
#数値欲しいとき
#H, W = map(int, input().split())
#文字欲しいとき
#str = input()
#文字分割
A,B,C = input().split()

if A == B == C:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

S = input()
tList = list(S)

firstStation = tList[0]
Monopoly = 0

for str in tList:
    if(str == firstStation):
        Monopoly = 0

    else:
        Monopoly = 1
        break

if(Monopoly == 0):
    print('No')
else:
    print('Yes')
from math import ceil
N = int(input())
t, s = str(N)[:-2], str(N)[-2:]
# print(t, s)
if int(t) >= ceil(int(s)/5):
    print(1)
else:
    print(0)

### FIXED CODE ###

from math import ceil
N = int(input())
if N < 100:
    print(0)
    exit()
t, s = str(N)[:-2], str(N)[-2:]
if int(t) >= ceil(int(s)/5):
    print(1)
else:
    print(0)
numof500 = int(input())
numof100 = int(input())
numof50  = int(input())
moneyneeded = int(input())
 
counter = 0
for i in range(numof500 + 1):
  for j in range(numof100 + 1):
  	for k in range(numof50 + 1):
      if 500 * i + 100 * j + 50 * k == moneyneeded:
        counter += 1
 
print(counter)

### FIXED CODE ###

numof500 = int(input())
numof100 = int(input())
numof50  = int(input())
moneyneeded = int(input())
 
counter = 0
for i in range(numof500 + 1):
  for j in range(numof100 + 1):
    for k in range(numof50 + 1):
      if 500 * i + 100 * j + 50 * k == moneyneeded:
        counter += 1
 
print(counter)
r=map(int,input().split())
a=3(r*r)

### FIXED CODE ###

r=int(input())
a=3*(r*r)
print(a)
import math
a,b=map(int,input().split())
ax=set(range(math.ceil(25*a/2),math.floor(25*(a+0.99999)/2)+1))
bx=set(range(math.ceil(10*b),math.floor(10*(b+0.99999)))+1)
x=list(ax&bx)
if x:
  print(x[0])
else:
  print(-1)

### FIXED CODE ###

import math
a,b=map(int,input().split())
for i in range(2000):
  if math.floor((i+1)*0.08)==a and math.floor((i+1)*0.1)==b:
    print(i+1)
    exit()
print(-1)
import sys

N, W = map(int, input().split())
WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
'''
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
'''
INF = 10**11+1
dp = [[INF]*(N+1) for j in range(N*(10**3)+10)]
i = 0
ans = INF
while(True):
        for j in range(1, N+1):
                #print(i, j)
                w = WV[j-1][1]
                if i-w >= 0:
                        dp[i][j] = min(dp[i][j-1], dp[i-w][j-1]+WV[j-1][0])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = min(dp[i][j-1], WV[j-1][0])
        #print(dp[i][N])
        #print(i, dp[i][N])
        if dp[i][N] > W and ans <= W:
                print(i)
                exit()
        ans = dp[i][N]
        '''
        if dp[i][N] >= W:
                if ans == 0:
                        ans = dp[i][N]
                elif ans < dp[i][N]:
                        print(i)
                        exit()
                print(i, ans)
        '''
        i += 1

### FIXED CODE ###

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

dp = [0]*N

dp[1] = abs(H[1]-H[0])
for i in range(2, N):
    dp[i] =  min(dp[i-2]+abs(H[i]-H[i-2]), dp[i-1]+abs(H[i]-H[i-1]))

print(dp[N-1])
data = input().split()
a = int(data[0])
b = int(data[1])

if b%a == 0:
  print(a+b)
  else:
    print(b-a)

### FIXED CODE ###

data = input().split()
a = int(data[0])
b = int(data[1])

if b%a == 0:
  print(a+b)
else:
  print(b-a)
s = input()
ans = []
cnt = 0
for i in range(len(s)):
  if s[i] in set("ATCG"):
    cnt += 1
  else:
    ans.append(cnt)
    cnt = 0
print(max(ans))

### FIXED CODE ###

s = input()
ans = []
cnt = 0
for i in range(len(s)):
  if s[i] in set("ATCG"):
    cnt += 1
    ans.append(cnt)
  else:
    ans.append(cnt)
    cnt = 0
print(max(ans))
z=input
print(z[:-8])

### FIXED CODE ###

z=input()
print(z[:-8])
N=int(input())
l=[]
for i in N:
  l.append(int(input()))
print(sum(l)-max(l)//2)

### FIXED CODE ###

N=int(input())
l=[]
for i in range(N):
  l.append(int(input()))
print(sum(l)-max(l)//2)
a=list(map(int,input().split()))
b=a.sorted
print(b[1]-b[0]+b[2]-b[1])

### FIXED CODE ###

a=list(map(int,input().split()))
b=sorted(a)
print(b[1]-b[0]+b[2]-b[1])
n = int(input())
a_list = list(map(int, input().split()))

status = True
execute = 0
while status:
    for i in range(n):
        if a_list[i] % 2 == 1:
            status = False
            break
        else:
            a_list[i] = a_list[i] / 2
    if status:
        execute += 1
print(execute)


### FIXED CODE ###

s = input()
counter = 0

for i in range(len(s)):
    if s[i] == '1':
        counter += 1
print(counter)
from functools import reduce
X, Y = map(int, input().split())
mod = 10**9+7

def comb(n, r):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    print(comb(num, p))


### FIXED CODE ###

# nCk(mod p)の計算
from math import factorial
X, Y = map(int, input().split())
MOD = 10**9+7
MAX = 10**6+1

 # a!のテーブルfact
fact = [0] * MAX
# (a!)^-1のテーブルfinv
finv = [0] * MAX

def comb_init():
    # a!と(a!)^-1のテーブルを作る
    # 累積積のイメージ
    fact[0] = fact[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, MAX):
        fact[i] = i * fact[i-1] % MOD
        finv[i] = pow(i, MOD-2, MOD) * finv[i-1] % MOD

def comb(n, r):
    return fact[n] * (finv[n-r] * finv[r] % MOD) % MOD    

n = (X+Y)//3
r = X-n
if not 0 <= r <= n:
    print(0)
    exit()

if (X+Y) % 3 != 0:
    print(0)
else:
    num = (X+Y)//3
    p = (Y - X + num) // 2
    q = (X + num - Y) // 2
    comb_init()
    print(comb(num, p))
n, m = map(int, input().split())
print("Yes") if n == M else print("No")

### FIXED CODE ###

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

print("Yes") if M == N else print("No")
import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [0]*(N+1)

for i in range(1,N+1):
    dp[i] = [max([dp[i-1][k]+ABC[i-1][j] for k in range(3) if j != k]) for j in range(3)]

print(max(dp[N]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
ABC = [list(map(int,input().split())) for i in range(N)]

dp = [[0]*3 for i in range(N+1)]

for i in range(1,N+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][j] = max(dp[i-1][k]+ABC[i-1][j],dp[i][j])

print(max(dp[N]))
def erase(x, y):
    c[y][x] = '0'
    for dx, dy in ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx <= w -1 and 0 <= ny <= h - 1:
            if c[ny][nx] == '1':
                erase(nx, ny)

while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    c = [[i for i in input().split()] for _ in range(h)]
    ans = 0
    for y in range(h):
        for x in range(w):
            if c[y][x] == '1':
                ans += 1
                erase(x, y)
    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
 
def erase(x, y):
    c[y][x] = '0'
    for dx, dy in ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < w and 0 <= ny < h and c[ny][nx] == '1':
            erase(nx, ny)
 
while True:
    w, h = map(int, input().split())
    if w == h == 0:
        break
    c = [input().split() for _ in range(h)]
    ans = 0
    for y in range(h):
        for x in range(w):
            if c[y][x] == '1':
                ans += 1
                erase(x, y)
    print(ans)
N = int(input())
h = list(map(int, input().split()))

#大きな値
INF = 9999

# DPtable
dp = [INF]*9999

#初期条件
dp[0] = 0
dp[1] = abs(h[1]-h[0])

#ループ
for i in range(N):
    if i == 0 or i == 1:
        continue
    else:
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))

print(dp[N-1])

### FIXED CODE ###

# N = int(input())
# h = list(map(int, input().split()))
# 
# #大きな値
# INF = 9999
# 
# # DPtable
# dp = [INF]*9999
# 
# #初期条件
# dp[0] = 0
# dp[1] = abs(h[1]-h[0])
# 
# #ループ
# for i in range(N):
#     if i == 0 or i == 1:
#         continue
#     else:
#         dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i]-h[i-2]))
# 
# print(dp[N-1])

N = int(input())
h = list(map(int, input().split()))
dp = [10 ** 10 for _ in range(N)]
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, N):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))

print(dp[-1])
import collections
import random
n=int(input())
a=list(map(int,input().split()))
if len(set(a))==1 and a[0]==0:
  print('Yes')
elif n%3!=0:
  print('No')
elif len(set(a))!=3:
    print('No')
else:
  print('Yes')
else:
  a=list(set(a))
  for i in range(len(a)):
    a[i]=format(a[i],'020b')
  l=[0 for i in range(20)]
  for i in range(len(a)):
    for j in range(20):
      if a[i][j]=='1':
        l[j]+=1
  ct=0
  for j in range(20):
    if l[j]==2 or l[j]==0:ct+=1
  if ct==20:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=format(a[i],'030b')
l=[0 for i in range(30)]
for i in range(n):
  for j in range(30):
    if a[i][j]=='1':
      l[j]+=1
for j in range(30):
  l[j]=l[j]%2
 
if 1 in l:
  print('No')
else:
  print('Yes')
N = int(input())


 def fibn(a, b, k, n):
     if k < n:
         return fibn(b, a+b, k+1, n)
     else:
         return a+b

 print(fibn(2,1,2,N))


### FIXED CODE ###

N = int(input())


def fibn(a, b, k, n):
    if k < n:
        return fibn(b, a+b, k+1, n)
    else:
        return a+b
if N == 1:
    print(1)
else:
    print(fibn(2,1,2,N))
from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 != 0:
    print(0)
    exit()

x_tmp=X
y_tmp=Y

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2

sum = x_count + y_count

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ret = cmb(sum, x_count) % (10**9+7)
print(ret)


### FIXED CODE ###

from operator import mul
from functools import reduce

X,Y = map(int,input().split()[:2])

if (X + Y) % 3 or not (X <= 2*Y and Y <= 2*X):
    print(0)
    exit()

x_tmp=X+1
y_tmp=Y+2

x_count=0
y_count=0

while x_tmp*2 != y_tmp:
    x_tmp-=2
    y_tmp-=1
    x_count+=1

y_count = y_tmp//2 - 1

sum = x_count + y_count

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, sum + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ret = cmb(sum,x_count,mod)
print(ret)
input()
xs=list(map(int, input().split()))

f,t,z=0,0,0
for x in xs:
  if x % 4 == 0:
    f+=1
  elif x % 2 == 0:
    t += 1
  else:
    z += 1
z += t
print('Yes' if z + 1 < f then 'No')


### FIXED CODE ###

input()
xs=list(map(int, input().split()))
 
f,t,z=0,0,0
for x in xs:
  if x % 4 == 0:
    f+=1
  elif x % 2 == 0:
    t += 1
  else:
    z += 1
z += 0<t
print('Yes' if z - 2 < f else'No')
import numpy as np

input = sys.stdin.readline

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

H = np.array(list(map(int, input().split())))

dp = np.zero(N, dtype=int)

for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[start:i]+np.abs(H[i]-H[start:i]))

print(dp[N-1])
    

### FIXED CODE ###

import numpy as np

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

H = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)

for i in range(1, N):
    start = max(0, i-K)
    dp[i] = min(dp[start:i]+np.abs(H[i]-H[start:i]))

print(dp[N-1])
a,b,c, = map(int, input().split())
if a > b > c >:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b,c = map(int, input().split())
if a < b < c:
  print("Yes")
else:
  print("No")
n = int(input())
s = [input() for _ in range(n)]
m = int(input())
t = [input() for _ in range(m)]
st = s + t
c = []
maxidx = 0
maxcount = -float('inf')

for i in set(st):
    count = s.count(i) - t.count(i)
    c.append((i, count))
    if count > maxcount:
        maxcount = count
        maxind = st.index(i)
        
if c[maxind][1] > 0:
    print(c[maxind][1])
else:
    print(0)

### FIXED CODE ###

n=[input() for _ in range(int(input()))]
m=[input() for _ in range(int(input()))]
l=list(set(n))
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))
A, B = input().strip()
print(B+A)

### FIXED CODE ###

A, B = input().split()
print(B+A)
n = int( raw_input() )
A = [0]
p = range(1, n)
a = [ [ 0 for i in xrange(n) ] for j in xrange(n) ]
for i in xrange(n):
    a[i] = map( int,raw_input().split() )
l = 0
while p != []:
    a_min = 2001
    for i in A:
        for j in p:
            if 0 <= a[i][j] < a_min:
                a_min = a[i][j]
                add_A = j
    A.append( add_A )
    NY.remove( add_A )
    l += a_min
print l

### FIXED CODE ###

n = int( raw_input() )
A = [0]
p = range(1, n)
a = [ [ 0 for i in xrange(n) ] for j in xrange(n) ]
for i in xrange(n):
    a[i] = map( int,raw_input().split() )
l = 0
while p != []:
    a_min = 2001
    for i in A:
        for j in p:
            if 0 <= a[i][j] < a_min:
                a_min = a[i][j]
                add_A = j
    A.append( add_A )
    p.remove( add_A )
    l += a_min
print l
def readQuestion(a,b):
    a,b=map(int,input().split())

# 解く
def solve(x):
    a,b=map(int,input().split())
    x=[]
    y=0
    high=0
    z=0
    u=0
    for i in range(1,1000):
        y+=i
        x.append(y)
    high = b-a
    z=high-1
    u=x[z]-b
    return u

# 全体
def main():
    x = readQuestion(a,b)
    answer = solve(x)
    print(answer)

# mainを呼び出す
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def readQuestion():
    line = sys.stdin.readline()
    sline = line.rstrip()
    [rline,r1line]=sline.split(" ")
    a=int(rline)
    b=int(r1line)
    return a,b 

def solve(a,b):
    x=[]
    y=0
    high=0
    z=0
    u=0
    for i in range(1,1000):
        y+=i
        x.append(y)
    high = b-a
    z=high-1
    u=x[z]-b
    return u
# 全体
def main():
    x,y = readQuestion()
    answer = solve(x, y)
    print(answer)

# mainを呼び出す
if __name__ == '__main__':
    main()
def calc():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * n for _ in range(n)]
	for i in range(n):
    	dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp[0][n-1]
ans = calc()
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

print(dp[0][n - 1])
N = int(input())
A = [input().split() for l in range(N)]
B = [input().split() for l in range(N)]
C = [input().split() for l in range(N-1)]
ans = 0

for i in range(N):
  ans = ans + B[A[i]]
  if i == 0:
    ans = ans
  else if A[i] == A[i-1] + 1:
    ans = ans + C[i]

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
 
point = sum(B)
for i in range(N-1):
  if A[i]==A[i+1]-1:
    point +=C[A[i]-1]
print(point)