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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]
result = 0
for i in range(n):
    h = True
    for x in range(n):
        if all(s[(x+i)%n][y]==s[(y+i)%n][x] for y in range(x, n)):
            continue
        else:
            h = False
            break
    if h:
        result += 1
print(result*n)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
result = 0
for i in range(n):
    h = True
    for x in range(n):
        if all(s[(x+i)%n][y]==s[(y+i)%n][x] for y in range(x, n)):
            continue
        else:
            h = False
            break
    if h:
        result += 1
print(result*n)
### BUGGY CODE ###

import math
import heapq
 
n,m = list(map(int,input().split()))
 
a = list(map(int,input().split()))
 
tmp = 0
 
for i in range(m):
 
        tmp = heapq.nlargest(1,a)
        a.remove(tmp[0])
        a.append(math.floor(tmp[0]/2))
 
 
print(sum(a))

### FIXED CODE ###

import heapq
import math

n,m = list(map(int,input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(a)

for i in range(m):
	tmp = heapq.heappop(a)
	tmp = (math.floor(-tmp/2)) * (-1)
	heapq.heappush(a, tmp)

print(sum(a) * -1)
### BUGGY CODE ###

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush, heapify
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
  k = int(input())
  ans = 0
  for a in range(1, k+1):
    for b in range(a, k+1):
      for c in range(b,k+1):
        if a==b and b==c:
          ans += gcd(gcd(a,b),c)
        elif a==b or b==c or c==a:
          ans += gcd(gcd(a,b),c) * 3
        else:
          ans += gcd(gcd(a,b),c) * 6
  print(ans)
  
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

from fractions import gcd
 
def main():
  k = int(input())
  ans = 0
  for a in range(1, k+1):
    for b in range(a, k+1):
      x = gcd(a,b)
      for c in range(b,k+1):
        if a==b and b==c:
          ans += a
        elif a==b or b==c:
          ans += gcd(x,c) * 3
        else:
          ans += gcd(x,c) * 6
  print(ans)
  
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

from collections import defaultdict
H, W, M = map(int, input().split())
hw = []
for _ in range(M):
    h, w = map(int, input().split())
    hw.append([h, w])

A = defaultdict(int)
B = defaultdict(int)
for i in range(M):
    A[hw[i][0]] += 1
    B[hw[i][1]] += 1

max_A = max(A.values())
max_B = max(B.values())

new_H = []
for i, v in A.items():
    if v == max_A:
        new_H.append(i - 1)

new_W = []
for i, v in B.items():
    if v == max_B:
        new_W.append(i - 1)

new_H.sort()
new_W.sort()
max_num = 0
for i in new_H:
    for j in new_W:
        if A[i + 1] == max_A and B[j + 1] == max_B:
            if [i + 1, j + 1] in hw:
                max_num = max(max_num, max_A + max_B - 1)
            else:
                max_num = max(max_num, max_A + max_B)

print(max_num)


### FIXED CODE ###

H, W, M = map(int, input().split())
hw = set()
sum_h = [0] * W
sum_w = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    hw.add((h, w))
    h -= 1
    w -= 1
    sum_h[w] += 1
    sum_w[h] += 1


max_h = max(sum_h)
max_w = max(sum_w)

new_H = [h for h in range(H) if sum_w[h] == max_w]
new_W = [w for w in range(W) if sum_h[w] == max_h]

max_num = max_h + max_w - 1
for i in new_H:
    for j in new_W:
        if (i + 1, j + 1) not in hw:
            print(max_h + max_w)
            exit()
        else:
            continue
        break

print(max_num)
### BUGGY CODE ###

S=input()
K=int(input())

T=set()
N=len(S)
for  i in range(N):
    for j in range(i,N):
        if S[i:j+1] not in T:
            T.add(S[i:j+1])
T=sorted(list(T))
print(T[K-1])


### FIXED CODE ###

from bisect import insort

S=input()
K=int(input())

T=[]
N=len(S)
for  i in range(N):
    V=""
    for j in range(i,min(i+K,N)):
        V+=S[j]
        if V not in T:
            insort(T,S[i:j+1])
            T=T[:K]
print(T[-1])
### BUGGY CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
ans = []
f = N-K+1
for i in range(f):
    ans.append(sum(p[i : i + K]))
print((max(ans) + K) / 2)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]
s = sum(p[0 : K])
ans = sum(p[0 : K])
f = N-K+1
for i in range(1, f):
    s = s - p[i-1] + p[i + K - 1]
    if ans <= s:
        ans = s
print((ans + K) / 2)
### BUGGY CODE ###

from bisect import insort_left

X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
i = 0
j = 0
k = 0
while(True):
    if i == len(R):
        break
    if P[j] > Q[k]:
        if Q[k] < R[i]:
            insort_left(Q, R[i])
            k += 1
            i += 1
            continue
    else:
        if P[j] < R[i]:
            insort_left(P, R[i])
            j += 1
            i += 1
            continue
    break
print(sum(P[j:]) + sum(Q[k:]))

### FIXED CODE ###

import heapq
 
X, Y, A, B, C = [int(i) for i in input().split()]
P = sorted([int(i) for i in input().split()])[-X:]
Q = sorted([int(i) for i in input().split()])[-Y:]
R = sorted([int(i) for i in input().split()])[::-1]
heapq.heapify(P)
heapq.heapify(Q)
i = 0
while(True):
    if P[0] >= R[i] and Q[0] >= R[i]:
        break
    if P[0] > Q[0]:
        if Q[0] < R[i]:
            heapq.heappop(Q)
            heapq.heappush(Q, R[i])
    else:
        if P[0] < R[i]:
            heapq.heappop(P)
            heapq.heappush(P, R[i])
    i += 1
    if i == len(R):
        break
print(sum(P) + sum(Q))
### BUGGY CODE ###

import sys, string
alpha = 'abcdefghijklmnopqrstuvwxyza'
tbl = string.maketrans(alpha[:-1], alpha[1:])
for s in sys.stdin:
  while not('the' in s or 'this' in s or 'than' in s):
    s = s.translate(tbl)
  print s[:-1]

### FIXED CODE ###

import sys, string
alpha = 'abcdefghijklmnopqrstuvwxyza'
tbl = string.maketrans(alpha[:-1], alpha[1:])
for s in sys.stdin:
  while not('the' in s or 'this' in s or 'that' in s):
    s = s.translate(tbl)
  print s[:-1]
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)
	#print(a,b)

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		#来たときは絶対に初回
		res = [node]
		ident = histind
		while res[len(res)-1]!=1:
			res.append(hist[ident][1])
			ident = hist[ident][0]
		allres.append(res[::-1])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				#endlist更新
				endlist[v] -= 1
		continue
	return None

#print_map(path)
result = bfs(path, 1, [1] * (N+1), N)
#print(result)
if result is None:
	print("No")
	exit(0)
print("Yes")
maxlen = len(result[len(result)-1])
for i in result[::-1]:
	for ind,v in enumerate(i[::-1]):
		if v == 1:
			break
		if ans[v] == 0:
			ans[v] = i[len(i)-2-ind]

for i in ans[2:]:
	print(i)


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
#from operator import itemgetter
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
N, M = LI()
AB = [LI() for _ in range(M)]
path = [[] for _ in range(N+1)]
mp = []
ans = [0] * (N+1)

for ab in AB:
	a = ab[0]
	b = ab[1]
	path[a].append(b)
	path[b].append(a)
	#print(a,b)

def bfs(tree, st, endlist, endnum):
	queue = collections.deque()
	queue.append([-1,st])
	endlist[st] -= 1
	now = [-1,-1,-1]
	pre = []
	depth = 0
	histind = -1
	node = -1
	hist = []
	res = []
	allres = []
	while queue:
		pre = now[:]
		now = queue.popleft()
		histind = now[0]
		node = now[1]
		hist.append([histind,node])
		#来たときは絶対に初回
		res = [node,hist[histind][1]]
		allres.append(res[::])
		endnum -= 1
		if endnum == 0:
			return allres
		for v in path[node]:
			if endlist[v] > 0:
				queue.append([len(hist)-1,v])
				#endlist更新
				endlist[v] -= 1
		continue
	return None

#print_map(path)
result = bfs(path, 1, [1] * (N+1), N)
#print("[TO, FROM] = {0}".format(result))
if result is None:
	print("No")
	exit(0)
print("Yes")
execnum = N
maxlen = len(result[len(result)-1])
for i in result:
	#print(i)
	if ans[i[0]] == 0:
		ans[i[0]] = i[1]
		execnum-=1
		if execnum == 0:
			break

for i in ans[2:]:
	print(i)
### BUGGY CODE ###

import sys,gc

    
A=[]
n=int(raw_input())
while n:
    s = (raw_input().split())
    if s[0] == 'insert':
        A.insert(0,int(s[1]))
    elif s[0] == 'delete':
        try:
            A.remove(int(s[1]))
        except:
            pass
    elif s[0] == 'deleteFirst':
        A.pop(0)
    elif s[0] == 'deleteLast':
        A.pop()
    n -=1
    
for e in A:
    print e,

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = np.zeros(N, dtype='int32')

for _ in range(min(K, 45)):
    lights = np.zeros(N, dtype='int32')
    for i, flash in enumerate(A):
        front = i-flash if i-flash >= 0 else 0
        back = i+flash if i+ flash < N else N-1
        lights[front:back+1] += 1
    A = np.copy(lights)

for i in A:
    print(int(i),end=' ')
print()

### FIXED CODE ###

import copy
N, K = map(int, input().split())
A = list(map(int, input().split()))
lights = [0] * N

for _ in range(min(K, 42)):
    lights = [0] * N
    for i, flash in enumerate(A):
        lights[max(0, i-flash)] += 1
        if i+flash < N-1:
            lights[i+flash+1] -= 1
    for i in range(1, N):
        lights[i] += lights[i-1]
    A = copy.deepcopy(lights)

for i in A:
    print(int(i),end=' ')
print()
### BUGGY CODE ###

from sys import stdin

n = int(stdin.readline().rstrip())
li = list(int(stdin.readline().rstrip()) for _ in range(n))

for i in range(n-1):
    if max(li) == li[i]:
        if i == 0:
            a = [0]
            b = li[i+1:]
        else:
            a = li[:i]
            b = li[i+1:]
        print(max(max(a),max(b)))
    else:
        print(max(li))
print(max(li[:n])) 

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
a_m = max(a)
a_i = a.index(a_m)
a.sort()
for i in range(len(a)):
  if i == a_i:
    print(a[-2])
  else:
    print(a_m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
graph=[[] for i in range(3*n)]
for i in range(m):
    a,e=map(int,input().split())
    graph[a-1].append(e+n-1)
    graph[a+n-1].append(e+2*n-1)
    graph[a+2*n-1].append(e-1)
s,t=map(int,input().split())
s-=1;t-=1
visited=[False]*(3*n)
dfs_alpha_memory = [3*n]*(3*n)
skipped = [set() for _ in range(3*n) ]

def dfs(checking, alpha=3*n):
    if dfs_alpha_memory[checking] < alpha:
        return dfs_alpha_memory[checking]
    looped = set()
    visited[checking]=True
    initial_alpha = alpha
    for next in graph[checking]:
        if t==next:
            alpha=1
            break
        if visited[next]:
            looped.add(next)
            continue
        alpha=min(alpha, dfs(next, alpha-1)+1)
    else:
        if alpha >= initial_alpha:
            alpha = 3*n
    skipped[checking] &= looped
    dfs_alpha_memory[checking] = min(alpha, dfs_alpha_memory[checking])
    visited[checking] = False
    return alpha

ans = dfs(s)//3
if ans >= n:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
inpl = lambda: list(map(int,input().split()))

N, M = inpl()
uv = [ set() for _ in range(3*N) ]
vu = [ set() for _ in range(3*N) ]
for _ in range(M):
    u, v = inpl()
    for k in range(3):
        uv[u-1 + k*N].add(v-1 + ((k+1)%3)*N)
        vu[v-1 + ((k+1)%3)*N].add(u-1 + k*N)
S, T = inpl()
S -= 1
T -= 1

cur = set({S})
for i in range(3*N):
    if i % 3 == 0 and T in cur:
        print(i//3)
        break
    elif len(cur) == 0:
        print(-1)
        break
    prev = cur
    cur = set()
    for u in prev:
        for fr in vu[u]:
            uv[fr].remove(u)
        cur |= uv[u]
else:
    print(-1)
### BUGGY CODE ###

import numpy as np
n,m,q = map(int,input().split())
list_lr = [list(map(int,input().split())) for i in range(m)]
list_pq = [list(map(int,input().split())) for i in range(q)]

query = np.zeros((501,501),dtype=int)

for k,l in list_lr:
    query[k][l] += 1

def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans

for k,m in list_pq:
    print(search(k,m))

### FIXED CODE ###

n,m,q = map(int,input().split())
query = [[0 for j in range(501)] for i in range(501)]

for h in range(m):
    k,l = map(int,input().split())
    query[k][l] += 1

#リストを累積和にする
for i in range(501):
    for j in range(501):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i][j-1]
for i in range(501):
    for j in range(501):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i-1][j]
        

for h in range(q):
    k,l = map(int,input().split())
    A,B,C = 0,0,0
    if k > 1:
        A = query[k-1][l]
        B = query[l][k-1]
        C = query[k-1][k-1]
    print(query[l][l] - A - B + C)
### BUGGY CODE ###

s = input()
dp = [0 for i in range(13)]
dp[0] = 1
c = 1000000007
m = 1
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in range(13)]
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                index = (j * m + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        j = int(s[i])
        for k in range(13):
            index = (j * m + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])


### FIXED CODE ###

s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    x = int(input())
    if x in A:
        A.remove(x)
    else:
        A.append(x)
print(len(A))

### FIXED CODE ###

from collections import Counter
N = int(input())
A,Ans = [],0
for i in range(N):
    A.append(int(input()))
cA = Counter(A).most_common()
for k,v in cA:
    if v%2 != 0:
        Ans += 1
print(Ans)
### BUGGY CODE ###

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


for i in range(N):
  if (i == 0):
    ans = a[0]
  else:
    ans = ans * a[i]

if (ans > 10**18):
  print('-1')
else:
  print(ans)

### FIXED CODE ###

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

ans = 1
for i in range(N):
  ans = ans * a[i]
  if (ans > 10 ** 18):
    break
  
if (ans > 10**18):
  if a.count(0) > 0:
    print(0)
  else:
    print(-1)
else:
  print(ans)
### BUGGY CODE ###

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

l = []
now = 1 # 今見ている数(1から見る配列を作りたいので1で初期化)
cnt = 0

# lには(1の個数),(0の個数),(1の個数),(0の個数),...(1の個数)という感じのリストを入れたい(両端が0から始まるとしても1が0こあるとしてカウントしたい)
for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now # 0と1を切り替える(now ^= 1でも良い)
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: # (1の個数),(0の個数),(1の個数),(0の個数),...(0の個数)となってしまっていたら最後に0を入れておく
    l.append(0)
# print(l)

ans = 0
width = 2 * K + 1

for i in range(0, len(l), 2):
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): # leftからright-1まで
        tmp += l[j]
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

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

l = []
now = 1 # 今見ている数(1から見る配列を作りたいので1で初期化)
cnt = 0

# lには(1の個数),(0の個数),(1の個数),(0の個数),...(1の個数)という感じのリストを入れたい(両端が0から始まるとしても1が0こあるとしてカウントしたい)
for i in range(N):
    if int(S[i]) == now:
        cnt += 1
    else:
        l.append(cnt)
        cnt = 1
        now = 1 - now # 0と1を切り替える(now ^= 1でも良い)
if cnt != 0:
    l.append(cnt)
if len(l) % 2 == 0: # (1の個数),(0の個数),(1の個数),(0の個数),...(0の個数)となってしまっていたら最後に0を入れておく
    l.append(0)
# print(l)

ans = 0
width = 2 * K + 1

left = 0
right = 0
tmp = 0 # [left, right)の総和
for i in range(0, len(l), 2):
    nextleft = i # 0,2,4,...
    nextright = min(i + width, len(l)) # 0+width,2+width,...
    while nextleft > left:
        tmp -= l[left]
        left += 1
    while nextright > right:
        tmp += l[right]
        right += 1
    ans = max(ans, tmp)

"""
# 愚直に足し算を繰り返すとTLE
for i in range(0, len(l), 2): # ここを2ごとにすることで1の個数を数えられる
    tmp = 0
    left = i
    right = min(i + width, len(l))
    for j in range(left, right): # leftからright-1まで
        tmp += l[j]
    ans = max(ans, tmp)
"""

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

n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n
inf = 1 << 30

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

if k < n:
	for i in range(k, n):
		smallest = inf
		for j in range(i - k, i):
			smallest = min(smallest, dp[j] + abs(hs[i] - hs[j]))
		dp[i] = smallest

print(dp[n-1])

### FIXED CODE ###

n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

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

n = int(input())

a = list(map(int, input().split()))
b = []

for i in range(n):
    t = i%2
    if t == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])

if n%2 == 1:
    for i in range(int(n/2)):
        b[i], b[-(i+1)] = b[-(i+1)], b[i]
    
for i in range(n):
    print(b[i], end=' ')

### FIXED CODE ###

n = int(input())

a = list(map(int, input().split()))
b = [None]*n

half = int(n/2)
for i in range(1,n+1):
    t = i%2
    if t != 0:
        b[half+int(i/2)] = a[i-1]
    else:
        b[half-int(i/2)] = a[i-1]

if n%2 == 1:
    for i in range(1,n+1):
        print(b[-i], end=' ')
else:
    for i in range(n):
        print(b[i], end=' ')
### BUGGY CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = []
for i in range(N):
    m.append(int(S[i:]) % P)
    
mc = Counter(m)

for n, v in mc.items():
    if v > 1:
        sum += v*(v-1)/2

sum += mc[0]

print(int(sum))

### FIXED CODE ###

from collections import Counter

N, P = map(int, input().split())
S = input()

sum = 0
if P == 2 or P == 5:
    for i in range(N):
        if int(S[i]) % P == 0:
            sum += i+1
    print(sum)
    exit()

m = []
t = 1
q = 0
for i in range(N,0,-1):
    q = ((int(S[i-1]) % P) * t + q) % P
    m.append(q)
    t = (10 * t) % P
    
mc = Counter(m)

for v in mc.values():
    if v > 1:
        sum += v*(v-1)//2

sum += mc[0]

print(sum)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])
"""
for bc in BC:
    bc = [int(i) for i in bc]
"""
#print(BC)
sum = sum(A)
for bc in BC:
    count = 0
    if bc[0] == bc[1]:
        print(sum)
        continue
    else:
        for i in range(0,len(A)):
            if A[i] == bc[0]:
                A[i] = bc[1]
                count += 1
    #  print("A:",A)
        sum += (bc[1]-bc[0])*count
        print (sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC=[]
for i in range (0, Q):
    BC.append([int(i) for i in input().split()])

#print(BC)
yoso_count=[]
for i in range(1,10**5+1):
    yoso_count.append([i,0])

sum = 0
for a in A:
    yoso_count[int(a)-1][1] += 1
    sum += a

#print(yoso_count,sum)

for bc in BC:
    sum += (bc[1] - bc[0])*yoso_count[bc[0]-1][1]
    yoso_count[bc[1]-1][1] += yoso_count[bc[0]-1][1]
    yoso_count[bc[0]-1][1] = 0
    print(sum)
### BUGGY CODE ###

n = int(input())

s = []
cnt = [0] * n
for i in range(n):
  tmp = input()
  if tmp not in s:
    s.append(tmp)
  else:
    cnt[s.index(tmp)] += 1

_max = 0
for c in cnt:
  if _max < c:
    _max = c
results = []
for i in range(len(cnt)):
  if cnt[i] == _max:
    results.append(s[i])

results.sort()

for result in results:
  print(result)

### FIXED CODE ###

n = int(input())

dic = {}
for i in range(n):
  s = input()
  if s in dic:
    dic[s] += 1
  else:
    dic[s] = 1

_max = 0
for v in dic.values():
  if _max < v:
    _max = v
dic2 = sorted(dic.items())

for (k,v) in dic2:
  if v == _max:
    print(k)