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

S = str(input())
N = int(input())

order = []
state = True

for n in range(N):
    order.append(input().split())


for n in range(N):
    if order[n][0] == '2':
        if (order[n][1] == '1') == state:
            S = order[n][2] + S
        else:
            S = S + order[n][2]
    elif order[n][0] == '1':
        if state:
            state = False
        else:
            state = True


if state:
    out = S
else:
    out = S[::-1]

print(out)

### FIXED CODE ###

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

top = []
end = []


order = []
state = True

for n in range(N):
    order = input().split()
    if order[0] == '2':
        if (order[1] == '1') == state:
            top.append(order[2])
        else:
            end.append(order[2])
    elif state:
        state = False
    else:
        state = True


if state:
    S = ''.join(S)
    top = ''.join(top[::-1])
    end = ''.join(end)
    out = top + S + end
    
else:
    S = ''.join(S[::-1])
    top = ''.join(top)
    end = ''.join(end[::-1])
    out = end + S + top

print(out)
### BUGGY CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = 1<<i
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		print(1)
		return

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


if __name__ == '__main__':
	main()

### FIXED CODE ###

MOD = 10**9+7

memo = dict()
memo[0] = 1
def pow3(n):
	if n in memo:
		return memo[n]
	if n%2 == 0:
		tmp = pow3(n//2)
		memo[n] = tmp*tmp%MOD
		return memo[n]
	memo[n] = 3 * pow3(n-1)%MOD
	return memo[n]

def cul(i, p):
	cur = (1<<i)%MOD
	cur *= pow3(p)
	return cur % MOD

def solve(L):
	n = len(L)
	if L == "0":
		return 1
	if not "0" in L:
		return pow3(n)

	num_1 = 0
	pos = []
	for i in range(n):
		if L[i] == "1":
			num_1 += 1
			pos.append(n-i-1)

	ans = (2**num_1)%MOD
	for i, p in enumerate(pos):
		ans += cul(i, p)
		ans %= MOD

	return ans

def main():
	L = input()
	print(solve(L))


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

a,b = list(map(int, input().split()))
ans = 0

if 3*a < b:
  print(ans)
elif 3*a == b:
  print(1)
elif 3*a > b:
  for i in range(a+1):
    if i > b:
      break
    elif i == b:
      ans += 1
      continue
    elif i < b:
      if i+2*a < b:
        break
      elif i+2*a == b:
        ans += 1
        continue
      elif i+2*a > b:
        for j in range(a+1):
          if i+j > b:
            break
          elif i+j == b:
            ans += 1
            continue
          elif i+j < b:
            if i+j+a < b:
              break
            elif i+j+a == b:
              ans += 1
              continue
            elif i+j+a > b:
              for k in range(a+1):
                if i+j+k == b:
                  ans += 1
              
  print(ans)

### FIXED CODE ###

k,s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
  mx = min(k, s-x)
  mn = max(0, s-x-k)
  ans += max(0, mx-mn+1)
print(ans)
### BUGGY CODE ###

N, M = 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)

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

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N)

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

ans = 0
for k, v in uf.all_group_members().items():
    ans = max(ans, len(v))
print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

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

N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    A, B = map(int, input().split())
    uf.unite(A-1, B-1)

ans = max(uf.get_size(i) for i in range(N))
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in A]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        primes[p] = max(primes[p], c)

ans = 0
for pc in PC:
    b = 1
    for p, c in primes.items():
        b *= pow(p, c - pc[p], MOD)
        b %= MOD
    ans += b
    ans %= MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def lcm(n, m):
    return n * m // gcd(n, m)

L = A[0]
for a in A:
    L = lcm(L, a)

ans = 0
for a in A:
    ans += L // a

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

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
min sec
"""
# とりあえず愚直に書いてみる。
# Bは0、Wは1にする。
# ひっくり返す順番は関係なさそうなので考えない。
def main():
    S = input()
    N = len(S)
    S_list = [0]*N
    for i in range(N):
        if S[i] == "W":
            S_list[i] = 1
    counter = 0
    while True:
        no_BW = True
        for i in range(N-1):
            if S_list[i] == 0 and S_list[i+1] == 1:
                S_list[i] = 1
                S_list[i+1] = 0
                counter += 1
                no_BW = False
        if no_BW:
            break
    print(counter)

if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
min sec
"""
# とりあえず愚直に書いてみる。→TLEした。
# Bは0、Wは1にする。→必要ない。
# ひっくり返す順番は関係なさそうなので考えない。
"""
BWのn個の連続（長さ2n）は、n+(n-1)+(n-2)+...+1 = n(n+1)//2回の操作で、
n個のBとn個のWの連続に置き換えられる。
"""
"""
ようするにバブルソートをしている。
k番目のWが文字列Sのi文字目ならば、
その移動距離は、(i-k)回になる。
これを足せばよい。
"""

def main():
    S = input()
    N = len(S)
    counter = 0
    k = 0
    for i in range(N):
        if S[i] == "W":
            counter += (i-k)
            k += 1
    print(counter)

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

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    intersects = set()
    for i in range(m):
        o = list(map(int, input().split(" ")))
        l = []
        for k in range(o[0], o[1]+1):
            l.append(k)
        if i == 0:
            intersects = set(l)
        else:
            intersects = intersects & set(l)

    print(len(intersects))


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            lmax = o[0]
            rmin = o[1]
        else:
            lmax = max(lmax, o[0])
            rmin = min(rmin, o[1])

    print(rmin-lmax+1 if lmax <= rmin else 0)


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

import copy
import fractions
from functools import reduce
N=int(input())
A=list(map(int,input().split()))
l=1
for i in A:
    if len(A)>=3:
        B=copy.deepcopy(A)
        B.remove(i)
        l=max(reduce(fractions.gcd,B),l)
    else:
        l=max(i,l)
print(l)

### FIXED CODE ###

from  fractions import gcd
N=int(input())
A=list(map(int,input().split()))
L=[0]
R=[0]
ans=1
for i in range(N-1):
    R.append(gcd(R[-1], A[-1-i]))
    L.append(gcd(L[-1], A[i]))
print(max(gcd(l,r)for l,r in zip(L,R[::-1])))
### BUGGY CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c

mod = 10**9+7
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
ans = 0
c = cmb(n-1,k-1,mod)
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[i] * c
    ans += a[-i-1] * c
    ans %= mod
    c = c * (n-k-i)*pow((n-i-1),mod-2,mod)
if ans < 0:
    ans += mod
print(ans)

### FIXED CODE ###

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
mod = 10**9 + 7
n,k = map(int,input().split())
inv = [0,1]
for i in range(2,n):
  inv += [inv[mod % i]*(mod - mod//i) % mod]
a = list(map(int,input().split()))
a.sort()
ans = 0
c = 1
x = 1
if k == 1:
    print(0)
    exit()
for i in range(n-k+1):
    ans -= a[n-k-i] * c
    ans += a[k+i-n-1] * c
    ans %= mod
    c = c*(i+k)*inv[i+1] % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                count = max(count,alr[q[0]][q[1]] + 1)
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'

print(count)


### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                count = max(count,alr[q[0]][q[1]] + 1)
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'

print(count)
### BUGGY CODE ###

import itertools
import heapq
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
if n>=2*k:
  a_plus = heapq.nlargest(k, a)
  a_minus = heapq.nsmallest(k, a)
  a_new = a_plus+a_minus
  comb = itertools.combinations(a_new,k)
else:
  comb = itertools.combinations(a,k)
  
l = [list(i) for i in comb]
  
A = []
one = [1]*len(l)
for i in range(len(l)):
  for j in range(k):
    one[i]*=l[i][j]
    A.append(one[i])
    
l_max = max(one)
waru = 10**9 + 7
 
mod = l_max % waru
print(mod)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N,K=map(int,input().split())
    L=list()
    for i in range(K):
        l,r=map(int,input().split())
        for j in range(l,r+1):
            L.append(j)
    mod=998244353
    L.sort()

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

        for l in L:
            if i+l>N:
                break
            dp[i+l] +=dp[i]
            dp[i+l] %=mod

    print(dp[N-1])













if __name__ == "__main__":
    main()

# \n


### FIXED CODE ###

import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    L = [[] for _ in range(K)]
    for t in range(K):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            L[t].append(j)

    lc = [0] * K
    mod = 998244353

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

        for k in range(K):
            CL =L[k]
            if len(CL)==1:
                lc[k]=dp[i-CL[0]] %mod
            else:
                if CL[-1] > i:
                    lc[k] = lc[k] %mod +dp[i-L[k][0]] %mod
                else:
                    lc[k] =( lc[k] + dp[i - L[k][0]] - dp[i - L[k][-1]-1] )%mod
            dp[i] += lc[k]



    print(dp[N - 1]%mod)


if __name__ == "__main__":
    main()

# \n
### BUGGY CODE ###

from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  xwl=dict((c[0],i) for i,c in enumerate(xy))
  ywl=dict((c[1],i) for i,c in enumerate(xy))
  x=list(xwl.keys())
  y=list(ywl.keys())
  x.sort()
  y.sort()
  
  xdict=dict()
  ydict=dict()
  xdict[x[0]]=[1<<xwl[x[0]],0]
  ydict[y[0]]=[1<<ywl[y[0]],0]
  size=lambda x:sum(x>>i&1 for i in range(n))
  minus=lambda x,y:(x|y)^y
  for i in range(1,n):
    xdict[x[i]]=[xdict[x[i-1]][0]|(1<<xwl[x[i]]), xdict[x[i-1]][1]|(1<<xwl[x[i-1]])]
    ydict[y[i]]=[ydict[y[i-1]][0]|(1<<ywl[y[i]]), ydict[y[i-1]][1]|(1<<ywl[y[i-1]])]
  ans=float('inf')
  for s in range(n):
    for t in range(s+1,n):
      for u in range(n):
        for v in range(u+1,n):
          if size(minus(xdict[x[t]][0],xdict[x[s]][1])&\
                  minus(ydict[y[v]][0],ydict[y[u]][1]))>=k:
            ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

if __name__=='__main__':
  main()


### FIXED CODE ###

from collections import defaultdict
def main():
  n,k=map(int,input().split())
  xy=[list(map(int,input().split())) for _ in range(n)]
  x=[p[0] for p in xy]
  y=[p[1] for p in xy]
  x.sort()
  y.sort()
  
  s1=[[0]*n for _ in range(n)]
  s2=[[0]*n for _ in range(n)]
  s3=[[0]*n for _ in range(n)]
  s4=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
        for p in xy:
            if p[0]<=x[i] and p[1]<=y[j]:
              s1[i][j]+=1
              s2[i][j]+=(p[0]<x[i])
              s3[i][j]+=(p[1]<y[j])
              s4[i][j]+=(p[0]<x[i])*(p[1]<y[j])
  ans=float('inf')
  for s in range(n):
    for t in range(s+1,n):
      for u in range(n):
        for v in range(u+1,n):
          if s1[t][v]-s3[t][u]-s2[s][v]+s4[s][u]>=k:
            ans=min(ans,(x[t]-x[s])*(y[v]-y[u]))
  print(ans)

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

import math
from functools import reduce

k = int(input())
sum_ = 0

for i in range(1, k+1):
    if i == 1:
        sum_ += k ** 2
    else:
        for j in range(1, k+1):
            if j == 1:
                sum_ += k
            else:
                for l in range(1, k+1):
                    if l == 1:
                        sum_ += 1
                    else:
                        sum_ += reduce(math.gcd, [i, j, l])
            
print(sum_)

### FIXED CODE ###

import math

k = int(input())
sum_ = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        x = math.gcd(i, j)
        for l in range(1, k+1):
            sum_ += math.gcd(x, l)
            
print(sum_)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
max_s=-float("inf")

a1=a[0:n]
a_m=a[n:2*n]
a2=a[2*n:3*n]

a1.sort()
a2.sort()
base_sum=sum(a1)-sum(a2)

a1_vals=[0]*(n+1)
added=[]
j=0
for i in range(0,n):
  val=0
  if added != [] and added[-1] < a1[j] and added[-1] < a_m[i]:
    val=a_m[i]-added[-1]
    added.pop(-1)
    added.append(a_m[i])
    added.sort(reverse=True)
  elif a1[j] < a_m[i]:
    val=a_m[i]-a1[j]
    added.append(a_m[i])
    added.sort(reverse=True)
    j+=1
  a1_vals[i+1]=val+a1_vals[i]

a_m.reverse()
a2_vals=[0]*(n+1)
added=[]
j=-1
for i in range(0,n):
  val=0
  if added != [] and added[-1] > a2[j] and added[-1] > a_m[i]:
    val=a_m[i]-added[-1]
    added.pop(-1)
    added.append(a_m[i])
    added.sort(reverse=False)
  elif a2[j] > a_m[i]:
    val=a_m[i]-a2[j]
    added.append(a_m[i])
    added.sort(reverse=False)
    j-=1
  a2_vals[i+1]=val+a2_vals[i]

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val, (a1_vals[i] - a2_vals[n-i]))

print(base_sum + max_val)

### FIXED CODE ###

# 解説を確認、このような、最大（最小値）の出し入れが頻繁にあるデータでは、
# 「優先度付きキュー」というデータ構造を用いると容易になるようだ。
# 新規要素の Push & Pop が O(N log N) でできるとのこと。

from heapq import heapify,heappush,heappop

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

a1=a[0:n]
a_m=a[n:2*n]
a2=[ -x for x in a[2*n:3*n] ] # nega_list

a1_sums=[sum(a1)]
a2_sums=[sum(a2)]
heapify(a1)
heapify(a2)

# 左のシマに真ん中のシマを徐々に追加し、都度最小値を取り出す
for aa in a_m:
  heappush(a1,aa)
  p=heappop(a1)
  a1_sums.append(a1_sums[-1]+aa-p)

# 右のシマは都度最大値を取り出す
a_m.reverse()
for aa in a_m:
  heappush(a2,-aa)
  p=heappop(a2)
  a2_sums.append(a2_sums[-1]-aa-p)

max_val=-float("inf")
for i in range(0,n+1):
  max_val=max(max_val,a1_sums[i]+a2_sums[n-i])

print(max_val)
### BUGGY CODE ###

s = input()
init=[1]*len(s)
ans = [0]*len(s)
for _ in range(10**5):
    for i in range(len(s)-1):
        if s[i]=='R':
            ans[i+1]+=init[i]
    for i in range(1,len(s)):
        if s[i]=='L':
            ans[i-1]+=init[i]
    init = ans[:]
    ans = [0]*len(s)
print(*init)

### FIXED CODE ###

s=input()
init=[1]*len(s)

for k in range(len(s)-2):
    if s[k]=='R' and s[k+1]=='R':
        init[k+2]+=init[k]
        init[k]=0
for k in range(len(s)-1,0,-1):
    if s[k]=='L' and s[k-1]=='L':
        init[k-2]+=init[k]
        init[k]=0
print(*init)
### BUGGY CODE ###

import numpy as np

N, k = list(map(int, input().split()))
if k > N:
    k = N
hs = list(map(int, input().split()))
hs = [0] + hs

# init
dp = np.zeros(N + 1).astype(int)
dp[2] = abs(hs[2] - hs[1])

# loop
if N > 2:
    for i in range(3, N + 1):
        vals = []
        for j in range(1, k + 1):
            if i > j:
                vals.append(dp[i-j] + abs(hs[i] - hs[i-j]))
        dp[i] = min(vals)

# output
print(dp[N])

### FIXED CODE ###

import numpy as np

N, k = list(map(int, input().split()))
if k > N:
    k = N
hs = list(map(int, input().split()))
hs = np.array([0] + hs)

# init
dp = np.zeros(N + 1).astype(int)
dp[2] = abs(hs[2] - hs[1])

# loop
if N > 2:
    for i in range(3, N + 1):
        """
        for j in range(1, k + 1):
            if i <= j:
                continue
            if dp[i] == 0:
                dp[i] = dp[i-j] + abs(hs[i] - hs[i-j])
            else:
                dp[i] = min(dp[i-j] + abs(hs[i] - hs[i-j]), dp[i])
        """
        x = max(1, i - k)
        dp[i] = np.min(dp[x:i] + np.abs(hs[i] - hs[x:i]))

# output
print(dp[N])
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
city = []
table = [[] for i in range(N)]
for i in range(M):
  P, Y = map(int, input().split())
  city.append((P,Y))
  bisect.insort_left(table[P-1],Y)
for P, Y in city:
  x = str(bisect.bisect_left(table[P-1],Y)+1)
  P = str(P)
  ans = P.zfill(6)+x.zfill(6)
  print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
PY = [list(map(int,input().split())) for i in range(M)]
for i in range(M):
  PY[i].append(i)
  
PY.sort(key=lambda x:x[1])
pcount = {i:0 for i in range(1,N+1)}
ID = {i:"" for i in range(1,M+1)}

for i in range(M):
  pcount[PY[i][0]] += 1
  PY[i].append("{:0=6}".format(PY[i][0]) + "{:0=6}".format(pcount[PY[i][0]]))
PY.sort(key=lambda x:x[2])
for i in range(M):
  print(PY[i][3])
### BUGGY CODE ###

from collections import Counter
 
def verify_anagrams(first_word, second_word):
    def get_counter(s):
        return Counter(s.upper())
 
    return get_counter(first_word) == get_counter(second_word)

N = int(input())

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

for i in range(N):
  S[i] = input()
  
ans = 0

for i in range(N):
  for j in range(i+1,N):
    if verify_anagrams(S[i],S[j]) == True:
      ans += 1

print(ans)

### FIXED CODE ###

import collections
def resolve():
    N = int(input())
    S = [input() for i in range(N)]
    ans = 0

    for i in range(N):
        S[i]=str(sorted(S[i]))
    c = collections.Counter(S)
    for i in c.values():
        for j in range(1,i):
            ans += j
    print(ans)
    
resolve()
### BUGGY CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
r,g,b,n=IL()
ans=0
for i in range(0,n+1):
    for j in range(0,n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            ans+=1
            
print(ans)

### FIXED CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
r,g,b,n=IL()
L=[r,g,b]
L.sort()
s,m,l=L
ans=0
for i in range(n//l+1):
    for j in range(n//m+1):
        if n-i*l-j*m<0:
            break
        elif (n-i*l-j*m)%s==0:
            ans+=1
            
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
A=[0]*(N+2)
A[0:2]=[0,1]

for i in range(N):
    if i+1 not in a:
        A[i+2]=(A[i]+A[i+1])%(10**9+7)
print(A[N+1])

### FIXED CODE ###

flag=0
N,M=map(int,input().split())
A=[-1]+[int(input()) for _ in range(M)]+[N+1]
mod=10**9+7
    
fib=[1,1]
for i in range(10**5):
    fib.append((fib[i]+fib[i+1])%mod)
    
for i in range(1,M):
    if A[i+1]==A[i]+1:
        flag=1

if flag==0:
    B=[A[i+1]-A[i]-2 for i in range(M+1)]
    ans=1
    for i in range(M+1):
        ans=(ans*fib[B[i]])%mod
    print(ans)
else:
    print(0)