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

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    S = input()
    Q = II()
    r = False
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            r ^= True
        else:
            if query[1] == '1':
                    if r:
                        S = S + query[2][::-1]
                    else:
                        S = query[2] + S
            else:
                if r:
                    S = query[2][::-1] + S
                else:
                    S = S + query[2]
    print(S[::-1] if r else S)
                



    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    S = input()
    Slist = [S]
    Q = II()
    Slist = ['']*Q+Slist+['']*Q
    left = Q-1
    right = Q+1
    r = False
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            r ^= True
        else:
            if query[1] == '1':
                    if r:
                        # S = ''.join([S,query[2]])
                        Slist[right] = query[2]
                        right += 1

                    else:
                        # S = ''.join([query[2],S])
                        Slist[left] = query[2]
                        left -=1
            else:
                if r:
                    Slist[left] = query[2]
                    left -=1
                else:
                    # S = ''.join([S,query[2]])
                    Slist[right] = query[2]
                    right += 1
    # print(S[::-1] if r else S)
    if r:
        Slist[Q] = Slist[Q][::-1]

    print(''.join(Slist[::-1]) if r else ''.join(Slist))
                



    

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

# 入力
N = int(input())
S = [list(input()) for _ in range(N)]

# 解は、B = 0として、A = 0, 1, ..., N - 1 のうち、よい盤面になるものの個数のN倍
ans = N * sum(
    all(
        S[i][j] == S[(j - A) % N][(i + A) % N]
        for i in range(N)
        for j in range(i + 1)
    )
    for A in range(N)
)

# 出力
print(ans)


### FIXED CODE ###

# 入力
N = int(input())
S = [list(input()) for _ in range(N)]

# 解は、B = 0として、A = 0, 1, ..., N - 1 のうち、よい盤面になるものの個数のN倍
ans = N * sum(
    all(
        S[i][j] == S[(j - A) % N][(i + A) % N]
        for i in range(N)
        for j in range(N)
    )
    for A in range(N)
)

# 出力
print(ans)
### BUGGY CODE ###

n = int(input())

vary = []

for i in range(n):
    char = input()
    if char not in vary:
        vary.append(char)

print(len(vary))


### FIXED CODE ###

n = int(input())

vary = []

for i in range(n):
    vary.append(input())

uni = list(set(vary))

print(len(uni))
### BUGGY CODE ###

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

for i in range(N-1):
    for j in range(N-i-1):
        if A[i] == A[i+j+1]:
            print("NO")
            exit()

print("YES")

### FIXED CODE ###

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

for i in range(N-1):
    if A[i] == A[i+1]:
        print("NO")
        exit()

print("YES")
### BUGGY CODE ###

def MAIN():
    H, W = map(int, input().split())
    MAP = tuple(input() for _ in range(H))
    R, C = map(int, input().split())
    PTN = tuple(input() for _ in range(R))
    def solve(a, b):
        k = 0
        for i in range(a, a + R):
            if MAP[i][b:b + C] == PTN[k]:
                k += 1
            else:
                return False
        return True
    ans = []
    for i in range(H - R + 1):
        j = MAP[i].find(PTN[0])
        while j != -1:
            if solve(i, j):
                ans.append(f"{i} {j}")
            j = MAP[i].find(PTN[0], j + 1)
    if ans:
        print("\n".join(a for a in ans))
MAIN()



### FIXED CODE ###

base1 = 1009
base2 = 1013
mask = (1 << 32) - 1
def calc_hash(f, r, c):
    global ph, pw, h
    tmp = [[0] * c for _ in range(r)]
    dr, dc = r - ph, c - pw
    # t1 = 1
    t1 = (base1 ** pw) & mask
    # for _ in range(pw):
        # t1 = (t1 * base1) & mask
    for i in range(r):
        e = 0
        for j in range(pw):
            e = e * base1 + f[i][j]
        for j in range(dc):
            tmp[i][j] = e
            e = (e * base1 - t1 * f[i][j] + f[i][j + pw]) & mask
        tmp[i][dc] = e
    t2 = 1
    for _ in range(ph):
        t2 = (t2 * base2) & mask
    for j in range(dc + 1):
        e = 0
        for i in range(ph):
            e = e * base2 + tmp[i][j]
        for i in range(dr):
            h[i][j] = e
            e = (e * base2 - t2 * tmp[i][j] + tmp[i + ph][j]) & mask
        h[dr][j] = e
th, tw = map(int, input().split())
t = tuple(tuple(ord(c) for c in input()) for _ in range(th))
ph, pw = map(int, input().split())
p = tuple(tuple(ord(c) for c in input()) for _ in range(ph))
ans = []
if th >= ph and tw >= pw:
    h = [[0] * tw for _ in range(th)]
    calc_hash(p, ph, pw)
    key = h[0][0] & mask
    calc_hash(t, th, tw)
    for i in range(th - ph + 1):
        for j in range(tw - pw + 1):
            if h[i][j] & mask == key:
                ans.append(f"{i} {j}")
if ans:
    print("\n".join(a for a in ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    def calc(n, mod):
        f = 1
        for m in range(1, n + 1):
            f *= m
            f %= mod
        fn = f
        inv = pow(f, mod - 2, mod)
        invs = [1] * (n + 1)
        invs[n] = inv
        for m in range(n, 1, -1):
            inv *= m
            inv %= mod
            invs[m - 1] = inv 
        return fn, invs

    mod = 10**9+7
    n,a,b=map(int,input().split())
    ans=0
    fn,invs=calc(n,mod)
    for i in range(1,n+1):
        if i==a or i==b:
            continue
        else:
            ans+=(invs[i]*invs[n-i])%mod
    print((fn*ans)%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    mod = 10**9+7
    n,a,b=map(int,input().split())
    f=1
    fa=0
    for i in range(1,b+1):
        f=(f*(n-i+1)*pow(i,mod-2,mod))%mod
        if i==a:
            fa=f
    ans=(pow(2,n,mod)-fa-f-1)%mod
    print(ans)

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

#!/usr/bin/env python
# coding: utf-8

# In[63]:


N,Q=map(int,input().split())
S=input()
lr=[list(map(int,input().split())) for l in range(Q)]
ct=0
for i in range(Q):
    #t=S[lr[i][0]-1:lr[i][1]]
    #t=[S for j in range(lr[i][0],lr[i][1])]
    #print(t)
    for j in range(lr[i][0]-1,lr[i][1]-1):
        if S[j]=='A' and S[j+1]=='C':
            ct+=1
    print(ct)
    ct=0
   # if i==Q:
    #    break


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[4]:


N,Q=map(int,input().split())
S=input()
lr=[list(map(int,input().split())) for l in range(Q)]
ct=0
l=[0]*(N+1)
for i in range(0,len(S)-1):
    if S[i]=='A' and S[i+1]=='C':
        l[i+1]=1+l[i]
    else:
        l[i+1]=l[i]
for i in range(Q):
    print(l[lr[i][1]-1]-l[lr[i][0]-1])


# In[ ]:
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = format(a[i], '060b')
s = 0
for i in range(60):
    c = 0
    for j in range(n):
        if a[j][i] == '0':
            c += 1
    s += pow(2,59-i,MOD)*c*(n-c)%MOD
print(s%MOD)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]
for i in range(X):
  for j in range(Y):
    AB.append(A[i]+B[j])
AB.sort(reverse=True)
AB=AB[:K]

ABC=[]
for i in range(len(AB)):
  for j in range(Z):
    ABC.append(AB[i]+C[j])
ABC.sort(reverse=True)
ABC=ABC[:K]
for i in ABC:
  print(i)

### FIXED CODE ###

import heapq
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

seen=[(0,0,0)]
Q=[]
heapq.heappush(Q,[-(A[0]+B[0]+C[0]),0,0,0])
for _ in range(K):
  h=heapq.heappop(Q)
  i,j,k=h[1],h[2],h[3]
  print(-h[0])
  if i+1<X:
    if (i+1,j,k) not in seen:
      heapq.heappush(Q,[-(A[i+1]+B[j]+C[k]),i+1,j,k])
      seen.append((i+1,j,k))
  if j+1<Y:
    if (i,j+1,k) not in seen:
      heapq.heappush(Q,[-(A[i]+B[j+1]+C[k]),i,j+1,k])
      seen.append((i,j+1,k))
  if k+1<Z:
    if (i,j,k+1) not in seen:
      heapq.heappush(Q,[-(A[i]+B[j]+C[k+1]),i,j,k+1])
      seen.append((i,j,k+1))
### BUGGY CODE ###

#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    ans = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                ans += gcd(gcd(i, j), k)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
from math import gcd
from math import ceil, floor
sys.setrecursionlimit(10 ** 6)

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    ans = 0
    for a in range(1, n+1):
        for b in range(1, n+1):
            tmp = gcd(a, b)
            for c in range(1, n+1):
                ans += gcd(tmp, c)
    print(ans)

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

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch, Cw))

dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]
wps = [
    [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 0), (-1, -1), (-1, 1)],
    [(2, 2), (2, -1), (2, 0), (2, 1), (2, 0), (1, -1), (1, 1)],
    [(-2, 2), (-1, 2), (0, 2), (1, 2), (2, 2), (-1, 1), (1, 1)],
    [(-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2), (-1, -1), (1, -1)]
]

while q:
    d, i, j = heappop(q)
    used.add((i, j))

    if D[i][j] > d:
        D[i][j] = d
    else:
        continue

    for k, (di, dj) in enumerate(dirs):
        _i = i + di
        _j = j + dj
        if 0 <= _i < H and 0 <= _j < W:
            if (_i, _j) in used:
                continue
            used.add((i, j))
            if S[_i][_j] == '.':
                heappush(q, (d, _i, _j))
            else:
                for di, dj in wps[k]:
                    _i = i + di
                    _j = j + dj
                    if 0 <= _i < H and 0 <= _j < W and (_i, _j) not in used and S[_i][_j] == '.':
                        heappush(q, (d+1, _i, _j))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)


### FIXED CODE ###

from heapq import heapify, heappop, heappush
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di; J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

ans = D[Dh][Dw]
print(ans if ans < INF else -1)
### BUGGY CODE ###

n=int(input())
b=[]
for i in map(int, input().split()):
  b.append(i)
  b=b[::-1]
print(*b,sep=" ")
    

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],end=" ")
print(*A[N%2::2])
### BUGGY CODE ###

import bisect

A,B,Q=map(int,input().split())
slist = []
for i in range(A):
  slist.append(int(input()))
#print(slist)

tlist = []
for i in range(B):
  tlist.append(int(input()))
#print(tlist)

for i in range(Q):
  x = int(input())
  min_dist = 10**11
  
  # x->s->t
  if x < slist[0]:
    si = [0]
  elif slist[-1] < x:
    si = [len(slist)-1]
  else:
    sl = bisect.bisect(slist,x)
    si = [sl-1,sl]
    
  for index in si:
    s = slist[index]
    dist = abs(x-s)

    tl = bisect.bisect(tlist,s)
    if tl == 0:
      dist += abs(s-tlist[0])
    elif tl == len(tlist):
      dist += abs(s-tlist[len(tlist)-1])
    else:
      dist += min(abs(s-tlist[tl-1]),abs(s-tlist[tl]))
    
    if dist < min_dist:
      min_dist = dist

  # x->t->s
  if x < tlist[0]:
    ti = [0]
  elif tlist[-1] < x:
    ti = [len(tlist)-1]
  else:
    tl = bisect.bisect(tlist,x)
    ti = [tl-1,tl]
    
  for index in ti:
    t = tlist[index]
    dist = abs(x-t)

    sl = bisect.bisect(slist,t)
    if sl == 0:
      dist += abs(t-slist[0])
    elif sl == len(slist):
      dist += abs(t-slist[len(slist)-1])
    else:
      dist += min(abs(t-slist[sl-1]),abs(t-slist[sl]))
    
    if dist < min_dist:
      min_dist = dist

  print(min_dist)


### FIXED CODE ###

import bisect

A,B,Q=map(int,input().split())
slist = []
for i in range(A):
  slist.append(int(input()))
#print(slist)

tlist = []
for i in range(B):
  tlist.append(int(input()))
#print(tlist)

for i in range(Q):
  x = int(input())
  min_dist = 10**11
  
  # x->s->t
  if x < slist[0]:
    si = [0]
  elif slist[-1] < x:
    si = [len(slist)-1]
  else:
    sl = bisect.bisect(slist,x)
    si = [sl-1,sl]
    
  for index in si:
    s = slist[index]
    dist = abs(x-s)

    if s < tlist[0]:
      dist += tlist[0]-s
    elif tlist[-1] < s:
      dist += s-tlist[-1]
    else:
      tl = bisect.bisect(tlist,s)  
      dist += min(s-tlist[tl-1],tlist[tl]-s)
    
    if dist < min_dist:
      min_dist = dist

  # x->t->s
  if x < tlist[0]:
    ti = [0]
  elif tlist[-1] < x:
    ti = [len(tlist)-1]
  else:
    tl = bisect.bisect(tlist,x)
    ti = [tl-1,tl]
    
  for index in ti:
    t = tlist[index]
    dist = abs(x-t)

    if t < slist[0]:
      dist += slist[0]-t
    elif slist[-1] < t:
      dist += t-slist[-1]
    else:
      sl = bisect.bisect(slist,t)
      dist += min(t-slist[sl-1],slist[sl]-t)
    
    if dist < min_dist:
      min_dist = dist

  print(min_dist)
### BUGGY CODE ###

import queue
N,X,Y=map(int,input().split())

count=[0]*N

def bfs(start):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=queue.Queue()
    q.put([start,0])
    dist[start]=0
    while not q.empty():
        j,kyori=q.get()

        if j-1>=1:
            if dist[j-1]==-1:
                q.put([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.put([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.put([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.put([X,kyori+1])
            dist[X]=kyori+1

    return dist[1:]

def main():
    for start in range(1,N+1):
        #dist=bfs(start)
        for d in bfs(start):
            count[d]+=1

    for i in count[1:]:
        print(i//2)

main()

### FIXED CODE ###

from collections import deque
N,X,Y=map(int,input().split())

count=[0]*N

def bfs(start):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=deque()
    q.append([start,0])
    dist[start]=0
    while q:
        j,kyori=q.popleft()

        if j-1>=1:
            if dist[j-1]==-1:
                q.append([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.append([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.append([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.append([X,kyori+1])
            dist[X]=kyori+1

    return dist[1:]

def main():
    for start in range(1,N+1):
        dist=bfs(start)
        for d in dist:
            count[d]+=1

    for i in count[1:]:
        print(i//2)

main()
### BUGGY CODE ###

s = input()
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            R = "".join([R, a[2]])
        else:
            F = "".join([a[2], F])

ans = F + s + R
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])


### FIXED CODE ###

from collections import deque
d = deque()
d.extend(list(input()))
q = int(input())
z = 0
F = ""
R = ""
for i in range(q):
    a = tuple(input().split())
    if a[0] == "1":
        z += 1
        z %= 2
    else:
        if (int(a[1]) + z) % 2 == 0:
            d.append(a[2])
        else:
            d.appendleft(a[2])

ans = "".join(d)
if z % 2 == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

N,W=map(int,input().split())
v=[]
w=[]
for _ in range(N):
    ww,vv=map(int,input().split())
    v.append(vv)
    w.append(ww)

dp=[[0 for _ in range(W)] for _ in range(N)]

for h in range(W):
    if h+1>=w[0]:
        dp[0][h]=v[0]

for i in range(1,N):
    for j in range(W):
        if j+1>w[i]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[-1][-1])


### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
for _ in range(N):
    a,b=map(int,input().split())
    w.append(a)
    v.append(b)
V=sum(v)

dp=[[10**9 for _ in range(V+1)] for _ in range(N+1)]
dp[0][0]=0
ans=0

for i in range(N): #i番目の荷物を拾うかどうか
    for j in range(V+1): #価値jを超える重量の最小値
        dp[i+1][j]=min(dp[i][j],dp[i][max(0,j-v[i])]+w[i])
        if dp[i+1][j]<=W:
            ans=max(ans,j)
        
print(ans)
### BUGGY CODE ###

from math import ceil

N,A,B = map(int,input().split())
h = [int(input()) for _ in range(N)]

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            continue
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)

### FIXED CODE ###

from math import ceil

N,A,B = map(int,input().split())
h = sorted([int(input()) for _ in range(N)], reverse=True)

# C回以下の爆発で倒せるか
def is_all_kill(C:int):
    cnt = 0
    for HP in h:
        # あるモンスターに中心ダメージを何回与えるか
        tmp = ceil((HP-B*C)/(A-B))
        # オーバーキルの場合
        if tmp <= 0:
            break
        cnt += tmp
    return cnt <= C

ok = 10 ** 18
ng = 0
while ok - ng > 1:
    mid = (ok + ng) // 2
    if is_all_kill(mid):
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import sys
import math
mod=998244353
inf=float("inf")
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
@lru_cache(maxsize=10**10)
def karukosuu(x):
    if x==1:
        return 1 if int(s[0])%p==0 else 0
    res=1 if int(s[x-1])%p==0 else 0
    for i in range(x-1):
        if int(s[i:x])%p==0:res+=1
    return res+karukosuu(x-1)
n,p=map(int,input().split())
s=input()
print(karukosuu(n))
#TLEコードを投げてしまい申し訳ありません！！！！！！！！！！

### FIXED CODE ###

from collections import Counter
n,p=map(int,input().split())
A=list(map(int,input()))
def U(x):
    return int(A[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(A[i])%p==0:
            ans+=keta
    print(ans)
    exit()
    
acc = [0 for i in range(n)] 
cur = A[-1] % p
acc[-1] = cur
k = 1
for i in range(n-2, -1, -1):
    cur += pow(10, k, p) * A[i]
    cur %= p
    acc[i] = cur
    k += 1
acc = acc + [0]
 
C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
point_list = [K]*N
for answer in A:
    point_list = list(map(lambda x: x-1, point_list))
    point_list[answer-1] += 1
    
for ans in point_list:
    if ans > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
seikaisuu = [0]*N
for answer in A:
    seikaisuu[answer-1] += 1
for x in seikaisuu:
    if K > Q - x:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
ans=0
for x in range(n+1):
    y = math.floor(a*x/b) - a* math.floor(x/b)
    ans=max(ans,y)

print(ans)

### FIXED CODE ###

import math
a,b,n=map(int,input().split())

if n<b:
    print(math.floor(a*n/b))
else:
    print(math.floor(a*(b-1)/b))
### BUGGY CODE ###

s = input()
ans = 0
for j in range(4, len(s)):
    for i in range(len(s) - j + 1):
        x = int(s[i:i + j])
        if x % 2019 == 0:
            ans += 1
            i = i + j - 1
print(ans)


### FIXED CODE ###

S = input()
N = len(S)
SUM = [0] * (N + 1)
MOD = 2019

r = 1  # 10のi乗を2019で割った余り
S = S[::-1]
for i in range(N):
    A = r * int(S[i])
    SUM[i + 1] = (SUM[i] + A) % MOD
    r = r * 10 % MOD

cnt = [0] * 2019
ans = 0
for x in SUM:
    ans += cnt[x]
    cnt[x] += 1
print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    min_costs = [0 for i in range(N)]
    min_costs[1] = abs(h[1] - h[0])


    for i in range(2, N):
        min_cost = 1000000000
        for j in range(1, K+1):
            if i-j < 0: break
            cost = abs(h[i] - h[i-j]) + min_costs[i-j]
            if cost < min_cost:
                min_cost = cost
        min_costs[i] = min_cost

    
    print(min_costs[N-1])



if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    min_costs = [0 for i in range(N)]
    min_costs[1] = abs(h[1] - h[0])


    for i in range(2, N):
        min_cost = 1000000000
        for j in range(1, K+1):
            if i-j < 0: break
            cost = abs(h[i] - h[i-j]) + min_costs[i-j]
            if cost < min_cost:
                min_cost = cost
        min_costs[i] = min_cost

    
    print(min_costs[N-1])



if __name__ == '__main__':
    main()