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

S = list(input())
Q = int(input())
reverse = False
for _ in range(Q):
    tmp = input().split()
    if len(tmp) == 1:
        reverse = not reverse
    else:
        F = int(tmp[1])
        C = tmp[2]
        if F == 1:
            if reverse:
                S.append(C)
            else:
                S.insert(0, C)
        else:
            if reverse:
                S.insert(0, C)
            else:
                S.append(C)

if reverse:
    S.reverse()
print(''.join(S))

### FIXED CODE ###

S = list(input())
Q = int(input())
reverse = False
flont = []
for _ in range(Q):
    tmp = input().split()
    if len(tmp) == 1:
        reverse = not reverse
    else:
        F = int(tmp[1])
        C = tmp[2]
        if F == 1:
            if reverse:
                S.append(C)
            else:
                flont.append(C)
        else:
            if reverse:
                flont.append(C)
            else:
                S.append(C)
flont.reverse()
flont.extend(S)
if reverse:
    flont.reverse()
print(''.join(flont))
### BUGGY CODE ###

# s1 = input()
# len_s = len(s1)
# s2 = s1
# while True:
#     len_1 = len(s2)
#     s2 = s2.replace("01", "").replace("10", "")
#     len_2 = len(s2)
#     if len_1 == len_2:
#         break
#
# print(len_s - len(s2))

s = input()
s2 = s
# for i in range(len(s) // 2, 0, -1):
#     # print("i", i)
#     # print("s2", s2)
#     m1 = "1" * i + "0" * i
#     m2 = "0" * i + "1" * i
#     s2 = s2.replace(m1, "").replace(m2, "")

while True:
    len_1 = len(s2)
    a1 = "0000011111"
    a2 = "1111100000"
    if a1 in s2:
        s2 = s2.replace(a1, "")
    if a2 in s2:
        s2 = s2.replace(a2, "")

    a3 = "000111"
    a4 = "111000"
    if a3 in s2:
        s2 = s2.replace(a3, "")
    if a4 in s2:
        s2 = s2.replace(a4, "")

    a5 = "01"
    a6 = "10"
    if a5 in s2:
        s2 = s2.replace(a5, "")
    if a6 in s2:
        s2 = s2.replace(a6, "")
    # print(s2)

    len_2 = len(s2)
    if len_1 == len_2:
        break


print(len(s) - len_2)


### FIXED CODE ###

s = input()
ans = min(s.count('0'), s.count('1'))
print(ans * 2)
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
m=n//2

for i in range(n):
  data=x[:i]+x[i+1:]
  data.sort()
  print(data[m-1])

### FIXED CODE ###

n = int(input())
X = list(map(int, input().split()))
x = sorted(X)

res1 = x[n//2]
res2 = x[n//2 -1]

for i in range(n):
  if X[i] >= res1:
    print(res2)
  elif X[i] <= res2:
    print(res1)
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#n = int(input())
	n, k = IN()
	#s = input()
	al = LIN()
	cl=[mod]*n
	cl[0]=0
	for i, c in enumerate(al):
		#pa(cl)
		for j, nv in enumerate(al[i:i+k+1]):
			cl[i+j]=min(cl[i+j], cl[i]+abs(nv-c))
	
	print(cl[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
LIN=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#n = int(input())
	n, k = IN()
	#s = input()
	al = LIN()
	cl=[mod]*n
	cl[0]=0
	for i, c in enumerate(al):
		#pa(cl)
		for j, nv in enumerate(al[i:i+k+1]):
			cl[i+j]=min(cl[i+j], cl[i]+abs(nv-c))
	
	print(cl[-1])
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

class Dict(object):

    m1 = 1046527
    m2 = m1 - 1

    def __init__(self):
        self._dict = [""] * self.m1

    def insert(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == "":
                self._dict[ix] = k
                return
            else:
                i += 1

    def find(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == k:
                return True
            elif self._dict[ix] == "":
                return False
            else:
                i += 1

    def _h(self, k, i):
        return (self._h1(k) + i * self._h2(k)) % self.m1

    def _h1(self, k):
        return k % self.m1

    def _h2(self, k):
        return k % self.m2 + 1


def to_int(s):
    ret = 0
    i = 1
    for j in range(len(s)):
        e = s[len(s) - j - 1]

        if e == 'A':
            ret += 1 * i
        elif e == 'C':
            ret += 2 * i
        elif e == 'G':
            ret += 3 * i
        elif e == 'T':
            ret += 4 * i
        i *= 4

    return ret


if __name__ == '__main__':
    n = int(input())

    d = Dict()

    for _ in range(n):
        cmd, val = input().split()

        if cmd == "insert":
            d.insert(to_int(val))
        else:
            ans = "yes" if d.find(to_int(val)) else "no"
            print(ans)

### FIXED CODE ###

M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()
### BUGGY CODE ###

import numpy as np
N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = []

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while Tree != [[] for _ in range(N+1)]:
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.pop(0)
        Tree[child] = []
print(answer)

### FIXED CODE ###

import numpy as np
from collections import deque

N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = deque()

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != deque():
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.popleft()
print(answer)
### BUGGY CODE ###

a = input()
a = list(a)

s = 0
r = 1
l = 0
cnt = 0
while l <=len(a)-3:
    s = a[l]
    r =l
    while int(s)%2019 != 0 and r<=len(a)-2:
        #print(l,r)
        s +=a[r+1]
        if int(s)%2019 == 0:
            cnt +=1
        #print(s,cnt,l,r)   
        r += 1
    l +=1
print(cnt)

### FIXED CODE ###

s = input()[::-1]

mod = 2019
ans = 0
d = 0
L = [0]
memo = [0]
for i in s:
    S =str(i)
    tmp = int(S)*pow(10,d,mod)%mod
    tmp = L[-1] + tmp
    L.append(tmp%mod)
    d +=1

from collections import Counter
L = Counter(L)

for v in L.values():
    ans +=v*(v-1)//2
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
tree = [[] for _ in range(n)]
point = [0] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for _ in range(q):
    p, x = map(int, input().split())
    point[p-1] += x

q = [[0, 0]]
while True:
    if len(q) == 0:
        break
    child, parent = q.pop(0)
    p = point[child]
    for i in tree[child]:
        if i == parent:
            continue
        point[i] += p
        q.append([i, child])

print(*point)

### FIXED CODE ###

n, q = map(int, input().split())
tree = [[] for _ in range(n)]
point = [0] * n
for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

for _ in range(q):
    p, x = map(int, input().split())
    point[p-1] += x

stack = [[0, 0, -1]]
while stack:
  v, p, parent = stack.pop()
  point[v] += p
  for child in tree[v]:
    if child == parent:
      continue
    stack.append([child,point[v],v])

print(*point)
### BUGGY CODE ###

import itertools
N = int(input())
L = list(map(int, input().split()))
L = list(itertools.combinations(L, 3))

cnt = 0
for l in L:
    l = list(l)
    m = max(l)
    l.remove(m)
    if m < sum(l):
        cnt += 1
        
print(cnt)

### FIXED CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

#実家DPと気合い遷移式

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (not i|E|k) else N/(i+E+k)
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

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

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
b=[0]
for i in range(m):
    if b[-1:]<a[-1:]:
        temp=a.pop()
    else:
        temp=b.pop()
    temp=temp//2
    b.append(temp)
    b.sort()

print(sum(a)+sum(b))


### FIXED CODE ###

from heapq import heapify,heappop,heappush

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

N = 60
MOD = 10**9 + 7
n = int(input())
c0 = [0 for _ in range(N)]
c1 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) == 0:
            c0[j] += 1
        else:
            c1[j] += 1

ans = 0
for i in range(n-1):
    for j in range(N):
        if a[i] & (1 << j) == 0:
            c0[j] -=1
        else:
            c1[j] -=1
    for j in range(N):
        if a[i] & (1 << j) == 0:
            ans += (1<<j) * c1[j]
        else:
            ans += (1<<j) * c0[j]

print(ans % MOD)

### FIXED CODE ###

N = 60
MOD = 10**9 + 7
n = int(input())
# c1 = [0 for _ in range(N)]
c1 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] += 1
        # else:
        #     c1[j] += 1

ans = 0
for i in range(n-1):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] -=1
        # else:
        #     c0[j] -=1
    for j in range(N):
        if a[i] & (1 << j) != 0:
            ans += (1<<j) * (n-i-1-c1[j])
        else:
            ans += (1<<j) * c1[j]
            #ans += (1<<j) * c1[j]

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

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

S = [set() for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return set([i for i in range(self.n) if self.find(i) == root])
    

UFT = UnionFind(N)

for _ in range(M):
    A, B = map(int,input().split())
    S[A-1].add(B-1)
    S[B-1].add(A-1)
    UFT.union(A-1,B-1)
for _ in range(K):
    C, D = map(int,input().split())
    S[C-1].add(D-1)
    S[D-1].add(C-1)

ans = []
for i in range(N):
    ans.append(UFT.size(i) - len(UFT.members(i) & S[i]) - 1)
print(*ans)

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

UFT = UnionFind(N)
ans = [0 for _ in range(N)]

for _ in range(M):
    A, B = map(int,input().split())
    ans[A-1] -= 1
    ans[B-1] -= 1
    UFT.union(A-1, B-1)

for _ in range(K):
    C, D = map(int,input().split())
    if UFT.same(C-1, D-1):
        ans[C-1] -= 1
        ans[D-1] -= 1

ans = [UFT.size(i) + ans[i] - 1 for i in range(N)]

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

import numpy as np

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

dp = np.zeros(shape=N + 1, dtype=np.int64)

if 2 * K > N:
    A = [N for _ in range(N)]
else:
    for k in range(K):
        for i in range(N):
            dp[max(0, i - A[i])] += 1
            dp[min(N, i + A[i] + 1)] -= 1
        A = dp.cumsum()[:-1]
        if np.all(A >= N):
            break
        dp *= 0

print(' '.join(map(str, A)))


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split(' '))
A = tuple(map(int, input().split(' ')))
indexes = np.arange(0, N)

dp = np.zeros(shape=N + 1, dtype=np.int64)

for k in range(K):
    np.add.at(dp, np.maximum(0, indexes - A), 1)
    np.add.at(dp, np.minimum(N, indexes + A + 1), -1)
    A = dp.cumsum()[:-1]
    if np.all(A == N):
        break
    dp *= 0

print(' '.join(map(str, A)))
### BUGGY CODE ###

import collections
def main():

    N = int(input())
    S = input()
    d = collections.defaultdict(list)
    for l in range(1, N+1):
        for i in range(N-l+1):
            d[S[i:i+l]].append([i, i+l-1])
    for s in d:
        d[s] = sorted(d[s], key = lambda x: x[0])

    ans = 0
    for s in d:
        if len(d[s]) > 1:
            i, j = d[s][0]
            k, l = d[s][-1]
            if j < k:
                ans = max(ans, j-i+1)
    return ans

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

### FIXED CODE ###

def main():

    N = int(input())
    S = input()
    dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
    ans = 0

    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if S[i-1] == S[j-1] and dp[i-1][j-1] < (j-i):
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
            else:
                dp[i][j] == 0
    return ans

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

import sys
input=sys.stdin.readline

N=int(input())
A=tuple(map(int,input().split()))

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-x*(x-1)*pow(2,c,mod))%mod
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N=int(input())
A=tuple(map(int,input().split()))

mod=10**9+7
X=[0]*61
for x in A:
    i=0
    while x!=0:
        X[i]+=x&1
        x>>=1
        i+=1
ans=0
for x in A:
    x%=mod
    ans=(ans+x)%mod
ans=(ans*(N-1))%mod

for c,x in enumerate(X):
    if x>=2:ans=(ans-(x*(x-1)%mod)*pow(2,c,mod))%mod
print(ans)
### BUGGY CODE ###

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

from functools import reduce
def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

def gcd_list(numbers):
  return reduce(gcd, numbers)

m = 0
for i in range(N):
  if i == 0:
    tmp = A[1:]
  elif i == N-1:
    tmp = A[:N-1]
  else:
    tmp = A[:i] + A[i+1:]
  #print(tmp)
  a = gcd_list(tmp)
  if a > m:
    m = a

print(m)



### FIXED CODE ###

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

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

L = []
R = []

for i in range(N-1):
  if i == 0:
    L.append(A[0])
  else:
    L.append(gcd(L[i-1], A[i]))

for i in range(N-1):
  if i == 0:
    R.append(A[N-1])
  else:
    R.append(gcd(R[i-1], A[N-1-i]))

M = []
for i in range(N):
  if i == 0:
    M.append(R[N-2])
  elif i == N-1:
    M.append(L[N-2])
  else:
    M.append(gcd(L[i-1], R[N-2-i]))

print(max(M))
### BUGGY CODE ###

from functools import reduce
from itertools import combinations

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

n = int(input())
factor = [1] + prime_factorize(n)

ans = int(1e13)
for i in range(1, len(factor)//2 + 1):
    for c in combinations(factor, i):
        a = reduce(lambda x,y:x*y, c)
        b = n // a
        ans = min(ans, a + b - 2)
print(ans)

### FIXED CODE ###

def factorize(n):
    a = []
    f = 2
    while f * f <= n:
        if n % f == 0:
            a.append((f, n//f))
        f += 1
    if not len(a):
        a.append((1, n))
    return a

n = int(input())
factor = factorize(n)

ans = int(1e13)
for fa in factor:
    a, b = fa
    ans = min(ans, a + b - 2)
print(ans)
### BUGGY CODE ###

h,n = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(n)]


ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
ans = 0

t = ls[0]
ans += (h//t[0])*t[1]
h %= t[0]

while h>0:
  ls = sorted(ls,key = lambda x: min(x[0],h)/x[1], reverse = True)
  t = ls[0]
  ans += (h//t[0])*t[1]
  h %= t[0]
print(ans)



### FIXED CODE ###

n,m=map(int, input().split())
s=[list(map(int, input().split())) for i in range(m)]
x=max(a for a,b in s)
dp=[0]*(n+x)
for i in range(0,n+x):
  if i>0:
    dp[i]=min(dp[i-a]+b for a,b in s)
print(min(dp[n:]))
### BUGGY CODE ###

#  入力
#  足場の高さ
n, k = list(map(int, input().split()))
h = list(map(int, input().split()))


#  方針
#  i番目の足場にいるという状態に対して
#  その足場に最も少ないコストを記録する．

#  A_Frog.pyでわかることだが，pythonはver2のappendを使う方が処理が早い
#  足場0のコストは0
dp = [0]

for i in range(1, n):
    #  i番目の足場のコストの候補
    temp = [dp[j] + abs(h[i] - h[j]) for j in range(i - k, i) if j >= 0]
    #  候補の最小値をコストに記録
    dp.append(min(temp))

print(dp[n - 1])


### FIXED CODE ###

import numpy as np

#  入力
n, k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))

#  方針
#  i番目の足場にいるという状態に対して
#  その足場に最も少ないコストを記録する．

dp = np.zeros(n, dtype=np.int)
for i in range(1, n):
    st = max(0, i - k)
    dp[i] = np.min(dp[st:i] + np.abs(h[i] - h[st:i]))

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

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
s=input()
q=int(input())
Q=map(int,input().split())
A=[]
data=[0]*(n+1)
for i,si in enumerate(s):
    if si == "D":
        A.append((i,count))
    elif si == "M":
        count+=1
    elif si == "C":
        for ai,ac in A:
            data[i-ai]+=count-ac
for i in range(len(data)-1):
    data[i+1]+=data[i] 
for qi in Q:
    print(data[qi-1])
# print(data)
          



### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
s=input()
q=int(input())
Q=map(int,input().split())
A=[-1]*(n+1)
C=[-1]*(n+1)
data=[0]*(n+1)
for i,si in enumerate(s):
    if si == "D":
        A[i]=count
    elif si == "M":
        count+=1
    elif si == "C":
        C[i]=count
# for i in range(len(data)-1):
#     data[i+1]+=data[i] 
for k in Q:
    count = ans = 0
    a_num=0
    for i in range(n):
        if A[i]!=-1:
            a_num+=1
            count+=A[i]
        if i-k>=0 and A[i-k]!=-1:
            a_num-=1
            count-=A[i-k]
        if C[i]!=-1:
            ans+=a_num*C[i]-count
    print(ans)
# print(A)
# print(C)
    
# print(data)