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

n = int(input())
hoge = [int(input()) for i in range(n)]

for i in range(len(hoge)):
    temp = hoge.copy()
    del temp[i]
    temp = set(temp)
    print(max(temp))

### FIXED CODE ###

n = int(input())
hoge = [int(input()) for i in range(n)]
max_value = max(hoge)
second_value = sorted(hoge)[-2]
if max_value == second_value:
    for i in range(len(hoge)):
        print(max_value)
else:
    for i in hoge:
        if i != max_value:
            print(max_value)
        else:
            print(second_value)
### BUGGY CODE ###

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

saeki = []
maxsaeki = 0
ans = 0

for i in range(len(a)-1):
    hikaku = a[i]
    m = max(a[i+1:])
    s = m - hikaku
    if s == maxsaeki:
        ans += 1
    if s > maxsaeki:
        ans = 1
        maxsaeki = s

print(ans)

### FIXED CODE ###

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

ma = a[-1]
m = 1
maxsaeki = 0
ans = 0

for i in range(n-2,-1,-1):
    if a[i] > ma:
        ma = a[i]
        m = 1
    elif a[i] < ma:
        if (ma - a[i]) > maxsaeki:
            maxsaeki = ma-a[i]
            ans = 1
        elif (ma - a[i]) == maxsaeki:
            ans += 1

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

n = int(input())
a = [int(x) for x in input().split()]
mult = 1
for i in range(n):
    mult *= a[i]
if mult > 1e+18:
    print(-1)
else:
    print(mult)


### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 1
 
for n in range(N):
 ans = L[n]*ans
 if ans >= 1000000000000000001: ans = -1
 if ans == -1: break
 
for n in range(N):
 if L[n] == 0: ans = 0
print(ans)
### BUGGY CODE ###


N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
value=0
mod=10**9 + 7
if K==1:
    print(0)
    exit()
z=1
for i in range(N):
    if i>=K-1:
        value+=z*A[i]
        z*=i-(K-1) + K
        z//=i-(K-1) + 1
    value%=mod
A.reverse()
z=1
for i in range(N):
    if i>=K-1:
        value-=z*A[i]
        z*=i-(K-1) + K
        z//=i-(K-1) + 1
    value%=mod

print(value)


### FIXED CODE ###

mod = 10**9 + 7
kaijotable = [0 for i in range(200100)]
kaijotable[0] = 1
for i in range(1, 200051):
    kaijotable[i] = (kaijotable[i - 1] * i) % mod

def doubling(x, y, mod):
    if y == 0:
        return 1
    if y == 1:
        return x
    elif y % 2 == 0:
        val = (doubling(x, y // 2, mod) ** 2) % mod
        return val
    else:
        val = (doubling(x, y // 2, mod) ** 2) * x % mod
        return val

def gyaku(x):
    gyaku = doubling(x, mod - 2, mod) % mod
    return gyaku

gyakutable = [0 for i in range(200100)]
gyakutable[200050] = gyaku(kaijotable[200050])
for i in range(200050, 0, -1):
    gyakutable[i - 1] = i * gyakutable[i] % mod

N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
value=0
mod=10**9 + 7
if K==1:
    print(0)
    exit()

z=0

for i in range(N):
    if i>=K-1:
        c=kaijotable[z+K-1] * gyakutable[K-1] * gyakutable[z+K-1-(K-1)] % mod
        value+=c*A[i]
        value-=c*A[N-1-i]

        z+=1
    value%=mod
print(value)
### BUGGY CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,k=map(int,input().split())
    a=sorted(map(int,input().split()))
    b=sorted(map(int,input().split()),reverse=1)
    #print(a,b)
    ok=max(a)*max(b)
    ng=-1
    
    def check(a,b,mid,k):
        if sum(a[i]-mid//b[i]for i in range(n) if a[i]*b[i]>mid)<=k:
            return 1
        else:
            return 0
            
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if check(a,b,mid,k):
            ok=mid
        else:
            ng=mid
    print(ok)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
 
def main():
    n,k=map(int,input().split())
    a=sorted(map(int,input().split()))
    b=sorted(map(int,input().split()),reverse=1)
    #print(a,b)
    ok=max(a)*max(b)
    ng=-1
    
    def check(a,b,mid,k):
        if sum(a[i]-mid//b[i]for i in range(n) if a[i]*b[i]>mid)<=k:
            return 1
        else:
            return 0
            
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if check(a,b,mid,k):
            ok=mid
        else:
            ng=mid
    print(ok)

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

import numpy as np
n, q = map(int, input().split())
a_b = [list(map(int, input().split())) for i in range(n-1)]
p_x = [list(map(int, input().split())) for i in range(q)]
xs = [0 for i in range(n)]
rin = np.array([[0 for i in range(n)] for j in range(n)])
for node in a_b:
    rin[node[0]-1][node[1]-1] = 1
def dfs(p, x):
    for c, d in enumerate(rin[p]):
        if d !=0:
            xs[c] +=x
            dfs(c, x)
    return xs
for ele in p_x:
    xs[ele[0]-1] +=ele[1]
    xs = dfs(ele[0]-1, ele[1])
xs = map(str, xs)
print(' '.join(xs))

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [deque([]) for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, bp=-1):
    while v[p]:
        c =v[p].popleft()
        if c ==bp:
            continue
        #print(p, c, bp)
        score[c]+=score[p]
        dfs(c, bp=p)
visited = [0]                
dfs(0)
print(*score)
### BUGGY CODE ###

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

def main():
    n = int(input())
    a_list = []
    for _ in range(n):
        num = int(input())
        if num in a_list:
            a_list.remove(num)
        else:
            a_list.append(num)
    print(len(a_list))


if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
from collections import Counter

def main():
    n = int(input())
    a_list = []
    for _ in range(n):
        a_list.append(int(input()))
    
    ans = 0
    cnt = Counter(a_list)
    for i in set(a_list):
        if cnt[i] % 2 != 0:
            ans += 1
    print(ans)



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

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

for i in range(K):
  data = [0]*N
  for j in range(N):
    if j-List[j] < 0:
      data[0] += 1
    else:
      data[j-List[j]] += 1
    if j+List[j]+1 < N:
      data[j+List[j]+1] +=-1
  List[0] = data[0]
  for j in range(N-1):
    List[j+1] = List[j] + data[j+1]
  if List.count(N) == N:
    break
print(*List)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N)%md
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N,md)
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

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

A,B,C,D=map(int,input().split())
cnt=0
for i in range(A,B+1):
    if i%C!=0 and i%D!=0:
        cnt+=1

print(cnt)

### FIXED CODE ###

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

B2=B-B//C-B//D+B//lcm(C,D)
A2=(A-1)-(A-1)//C-(A-1)//D+(A-1)//lcm(C,D)

print(B2-A2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) 
asl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    cl = list(map(int, input().split())) 
    s = 0
    for c in cl:
        s += 1<<(c-1)
    asl.append([a,s])

INF = 10**8
dp = [INF]*(2**N)
dp[0] = 0
for i in range(2**N):
    for as_v in asl:
        a, s = as_v
        dp[i|s] = min(dp[i]+a ,dp[i|s])

ans = dp[2**N-1]
if ans == INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N, M = map(int, input().split()) 
asl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    cl = list(map(int, input().split())) 
    s = 0
    for c in cl:
        s += 1<<(c-1)
    asl.append([a,s])

INF = 10**8
dp = [INF]*(2**N)
dp[0] = 0
for i in range(2**N):
    for as_v in asl:
        a, s = as_v
        dp[i|s] = min(dp[i]+a ,dp[i|s])

ans = dp[2**N-1]
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR() #初期状態 偶数席
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR() #最終状態 奇数
if rtmp == 'Vacant':
    exit()
while l < r:
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c + 1
        else:
            r = c - 1
    else:
        if tmp == ltmp:
            r = c - 1
        else:
            l = c + 1

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N

for i in range(N):
	A[i], B[i] = MAP()

max_A = max(A)
dp = [INF]*(H+max_A+1)
dp[0] = 0
for i in range(N):
	for j in range(A[i], H+max_A+1):
		dp[j] = min(dp[j], dp[j-A[i]]+B[i])

print(min(dp[H:]))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, N = MAP()
A = [0]*N
B = [0]*N

for i in range(N):
    A[i], B[i] = MAP()

dp = [[INF]*(H+max(A)+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+max(A)):
        if j < A[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])

print(min(dp[N][H:]))
### BUGGY CODE ###

import math
sum = 0
K = int(input())
for k in range(K):
  for j in range(K):
    for i in range(K):
      sum += math.gcd(math.gcd(k+1,j+1),i+1)
print(sum)

### FIXED CODE ###

from math import gcd
sum = 0
K = int(input())
for k in range(1,K+1):
  for j in range(1,K+1):
    t = gcd(k,j)
    for i in range(1,K+1):
      sum += gcd(t,i)
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

def main():
  n = int(input())
  U = n**2
  G = [[] for _ in range(U)]
  parent = [0]*U
  for i in range(n):
    A = list(map(lambda x:int(x)-1, input().split()))
    for j in range(n-2):
      a = A[j]
      b = A[j+1]
      G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
      parent[min(i, b)*n+max(i, b)] += 1

  que = deque([(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]])
  ans = 1
  cnt = 0
  while que:
    v, t = que.pop()
    ans = max(ans, t)
    cnt += 1
    for nv in G[v]:
      parent[nv] -= 1
      if not parent[nv]:
        que.appendleft((nv, t+1))
  if cnt == n*(n-1)//2:
    print(ans)
  else:
    print(-1)
    
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
U = n**2
G = [[] for _ in range(U)]
parent = [0]*U
for i in range(n):
  A = list(map(lambda x:int(x)-1, input().split()))
  for j in range(n-2):
    a = A[j]
    b = A[j+1]
    G[min(i, a)*n+max(i, a)].append(min(i, b)*n+max(i, b))
    parent[min(i, b)*n+max(i, b)] += 1

que = deque([(i*n+j, 1) for i in range(n-1) for j in range(i+1, n) if not parent[i*n+j]])
ans = 1
cnt = 0
while que:
  v, t = que.pop()
  ans = max(ans, t)
  cnt += 1
  for nv in G[v]:
    parent[nv] -= 1
    if not parent[nv]:
      que.appendleft((nv, t+1))
if cnt == n*(n-1)//2:
  print(ans)
else:
  print(-1)
### BUGGY CODE ###

import sys

def lcs_count(A,B):
    # initial value setting
    dp = [list(0 for _ in range(l2+1)) for _ in range(l1+1)]
    # create table
    for i in range(1,l1+1):
        for j in range(1,l2+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp

def lcs_string(dp):
    string = []
    S = [m for m in range(l1,0,-1)]
    T = [n for n in range(l2,0,-1)]
    for i,j in zip(S,T):
        if dp[i][j] > dp[i-1][j-1]:
            string.insert(0,s[i-1])
    print("".join(string))

s = sys.stdin.readline().rstrip()
t = sys.stdin.readline().rstrip()
l1 = len(s)
l2 = len(t)

DP = lcs_count(s,t)
lcs_string(DP)





### FIXED CODE ###

import sys

s = [ord(a)-97 for a in list(sys.stdin.readline().rstrip())]
t = [ord(b)-97 for b in list(sys.stdin.readline().rstrip())]
len_s = len(s)
len_t = len(t)

dp = [[0] * (len_t+1) for i in range(len_s+1)]
for i in range(len_s):
    for j in range(len_t):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

strings = []
while len_s > 0 and len_t > 0:
    if s[len_s-1] == t[len_t-1]:
        len_s -= 1
        len_t -= 1
        strings.insert(0,chr(s[len_s]+97))
    elif dp[len_s][len_t-1] > dp[len_s-1][len_t]:
        len_t -= 1
    else:
        len_s -= 1

print("".join(strings))
### BUGGY CODE ###

import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
import heapq

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = getInputInt()
data = getInputListInt()
l = len(data)

ans = []

for i in range(l-1, -1, -1):
    cnt = 0
    for j in ans:
        if j % (i+1) == 0:
            cnt += 1
    if data[i] != cnt % 2:
        ans.append(i+1)

if len(ans) == 0:
    print(0)
else:
    print(len(ans))
    print(*ans, sep=" ")



### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    b = [0 for i in range(n)]
    ans = []

    for i in range(n // 2, n):
        if a[i] == 1:
            b[i] = a[i]
            ans.append(i + 1)

    for i in range(n // 2 - 1, -1, -1):
        cnt = 0
        for j in range(i * 2 + 1, n, i + 1):
            cnt ^= b[j]
        if cnt != a[i]:
            b[i] = 1
            ans.append(i + 1)

    tmp = len(ans)
    print(tmp)
    if tmp > 0:
        print(*ans, sep=" ")


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

N, X = map(int, input().split())
S = list(map(int, input().split()))

numbers = S[:]

import math

def dps(numbers, x):
    min_n = min(numbers)
    if x < min_n:
        return x * math.factorial(len(numbers))
    
    if len(numbers) == 1:
        return x % numbers[0]
    
    ret = 0
    for i, n in enumerate(numbers):
        x_mod = x % n
        if x_mod == 0:
            ret += x_mod
        ret += dps(numbers[0:i] + numbers[i+1:], x_mod)
    return ret
        
ans = dps(numbers, X)
ans = ans % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

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

import math,heapq,sys
input = sys.stdin.readline
xs,ys,xe,ye = map(int,input().split())
cs = [(xs,ys,0), (xe,ye,0)]
N = int(input())
for i in range(N):
    cs.append(tuple(map(int,input().split())))

def calc_cost(i,j):
    if i == j: return float('inf')
    x1,y1,r1 = cs[i]
    x2,y2,r2 = cs[j]
    cost = max(0, math.hypot(x1-x2,y1-y2) - r1 - r2)
    return cost

INF = float('inf')
direct = calc_cost(0,1)
hq = []
for i in range(1,N+2):
    c = calc_cost(0,i)
    if c > direct: continue
    hq.append((c,i))
heapq.heapify(hq)
visited = [1] + [0] * (N+1)
cost = [0] + [INF] * (N+1)
while hq:
    c,v = heapq.heappop(hq)
    if v == 1:
        print(c)
        exit()
    cost[v] = c
    visited[v] = 1
    for to in range(1,N+2):
        if to == v or visited[to]: continue
        newcost = calc_cost(v, to)
        if cost[to] <= cost[v] + newcost: continue
        if direct < cost[v] + newcost: continue
        heapq.heappush(hq, (cost[v] + newcost, to))

### FIXED CODE ###

import math,heapq,sys
input = sys.stdin.readline
xs,ys,xe,ye = map(int,input().split())
cs = [(xs,ys,0), (xe,ye,0)]
N = int(input())
for i in range(N):
    cs.append(tuple(map(int,input().split())))

def calc_cost(i,j):
    if i == j: return float('inf')
    x1,y1,r1 = cs[i]
    x2,y2,r2 = cs[j]
    cost = max(0, math.hypot(x1-x2,y1-y2) - r1 - r2)
    return cost

INF = float('inf')
direct = calc_cost(0,1)
hq = []
for i in range(1,N+2):
    c = calc_cost(0,i)
    if c > direct: continue
    hq.append((c,i))
heapq.heapify(hq)
not_visited = set(range(1,N+2))
cost = [0] + [INF] * (N+1)
while hq:
    c,v = heapq.heappop(hq)
    if v not in not_visited: continue
    if v == 1:
        print(c)
        exit()
    cost[v] = c
    not_visited.remove(v)
    for to in not_visited:
        newcost = calc_cost(v, to)
        if cost[to] <= cost[v] + newcost: continue
        if direct < cost[v] + newcost: continue
        heapq.heappush(hq, (cost[v] + newcost, to))
### BUGGY CODE ###

N=int(input())
C=[[1000000000000 for x in range(N)] for y in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  C[a-1][b-1]=c
  C[b-1][a-1]=c
Q,K=map(int,input().split())
d=[1000000000000 for j in range(N)]
use=[0 for i in range(N)]
d[K-1]=0
while True:
  v=-1
  for i in range(N):
    if use[i]==0 and (v==-1 or d[i]<d[v]):
      v=i
  if v==-1:
    break
  use[v]=1
  for j in range(N):
    d[j]=min(d[j],d[v]+C[v][j])

for i in range(Q):
  x,y=map(int,input().split())
  print(d[x-1]+d[y-1])


### FIXED CODE ###

import heapq
from collections import defaultdict

N=int(input())
V=defaultdict(set)
for i in range(N-1):
  a,b,c=map(int,input().split())
  V[a-1].add((b-1,c))
  V[b-1].add((a-1,c))

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

def dijkstra(n,v):
  d=[float('inf')]*n
  d[v]=0
  
  hq=[(0,v)]
  
  while hq:
    u = heapq.heappop(hq)[1]
    for nv,c in V[u]:
      if d[nv]>d[u]+c:
        d[nv]=d[u]+c
        heapq.heappush(hq,(d[u]+c,nv))
        
  return d

ans=dijkstra(N,K-1)

for i in range(Q):
  a,b=map(int,input().split())
  print(ans[a-1]+ans[b-1])
### BUGGY CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  h = [int(i) for i in input().split()]

  minimumCost = [0] * N

  for currentIndex in range(1, N):
    minimumCost[currentIndex] = min(minimumCost[previousIndex] + abs(h[currentIndex] - h[previousIndex]) for previousIndex in range(max(currentIndex - K, 0), currentIndex))

  return minimumCost[N - 1]

print(solve())


### FIXED CODE ###

def solve():
  N, K = [int(i) for i in input().split()]
  H = [int(i) for i in input().split()]
  dp = [0] * N

  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))

  return dp[N - 1]

print(solve())