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

N,Q=map(int,input().split())
S=list(input())
S=[0]+S+[N+1]
TD= [list(input().split()) for _ in range(Q)]

def solve(place):
    if place == 0:
        return ('Left')
    elif place == N + 1:
        return ('Right')
    for td in TD:
        char,to=td
        if S[place]!=char:continue
        
        if to=='L':place-=1
        elif to=='R':place+=1
        
        if place==0:
            return('Left')
        elif place==N+1:
            return('Right')
    return('Not Drop')

l,r=0,N+1
L,R=0,N+1

while abs(r-l)>1:
    m=(l+r)//2
    if solve(m)=='Left':
        L=m
        l,r=m,r
    elif solve(m)=='Not Drop' or solve(m)=='Right':
        l,r=l,m

l,r=0,N+1

while abs(r-l)>1:
    m=(l+r)//2
    if solve(m)=='Right':
        R=m
        l,r=l,m
    elif solve(m)=='Not Drop' or solve(m)=='Left':
        l,r=m,r

print(max(R-L-1,0))


### FIXED CODE ###

N,Q=map(int,input().split())
S=list(input())
S=[0]+S+[N+1]
TD=[list(input().split()) for _ in range(Q)]

def solve(place):
    if place == 0:
        return ('Left')
    elif place == N+1:
        return ('Right')
    for td in TD:
        char,to=td
        if S[place]!=char:continue

        if to=='L':place-=1
        elif to=='R':place+=1

        if place==0:
            return('Left')
        elif place==N+1:
            return('Right')
    return('Not Drop')

l,r=0,N+1
L,R=0,N+1

while abs(r-l)>1:
    m=(l+r)//2
    if solve(m)=='Left':
        L=m
        l,r=m,r
    else:
        l,r=l,m

l,r=0,N+1

while abs(r-l)>1:
    m=(l+r)//2
    if solve(m)=='Right':
        R=m
        l,r=l,m
    else:
        l,r=m,r

print(max(R-L-1,0))
### BUGGY CODE ###

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

a = [i for i in A if A.count(i) >= 2]

if len(a) <= 1:
    print(0)
else:
    a = set(a)
    a = list(a)
    a.reverse()
    print(a[0]*a[1])


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ch = [0]*2
i = 0
j = 2
ans = 1
a.sort()
a = a[::-1]
while True:
    if a[i] == a[i+1]:
        ch[0] = a[i]
        break
    else:
        i += 1
    if i == n-1:
        ans = 0
        break

while True:
    if ans == 0:
        break
    if a[i+j] == a[i+j+1]:
        ch[1] = a[i+j]
        break
    else:
        j += 1
    if i+j == n-1:
        ans = 0

if ans == 0:
    print(0)
else:
    print(ch[0]*ch[1])
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = LI()
ans = float('INF')
for i in range(1,N):
    ans = min(ans,abs(sum(A[:i])-sum(A[i:])))
print(ans)


### FIXED CODE ###

import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = LI()
ans = float('INF')
sum_A = sum(A)
accumulate_A = list(itertools.accumulate(A))
for i in range(N-1):
    ans = min(ans,abs(sum_A-accumulate_A[i]*2))
print(ans)
### BUGGY CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb_flag = [[False for i in range(w)] for j in range(h)]

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb_flag[_h - 1][_w - 1] = True

h_max = max(h_cnt)
w_max = max(w_cnt)

max_h = []
max_w = []

for i in range(h):
  if h_cnt[i] == h_max:
    max_h.append(i)

for j in range(w):
  if w_cnt[j] == w_max:
    max_w.append(j)

flag = True

for i in max_h:
  for j in max_w:
    if not bomb_flag[i][j]:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)

### FIXED CODE ###

h, w, m = map(int, input().split())
h_cnt = [0 for i in range(h)]
w_cnt = [0 for i in range(w)]
bomb = set()

for i in range(m):
  _h, _w = map(int, input().split())
  h_cnt[_h - 1] += 1
  w_cnt[_w - 1] += 1
  bomb.add(((_h - 1),(_w - 1)))

h_max = max(h_cnt)
w_max = max(w_cnt)

max_h = []
max_w = []

for i in range(h):
  if h_cnt[i] == h_max:
    max_h.append(i)

for j in range(w):
  if w_cnt[j] == w_max:
    max_w.append(j)

flag = True

for i in max_h:
  for j in max_w:
    if (i, j) not in bomb:
      flag = False
      break

print(h_max + w_max - 1 if flag else h_max + w_max)
### BUGGY CODE ###


x = int(input())

for i in range(100):
    for j in range(100):
        if pow(i, 5)+pow(j, 5) == x:
            print(i, -j)
            exit()


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


a = 0
for i in make_divisors(x):
    a = i
    b = 0
    while pow(a, 5)-pow(b, 5) > x:
        if pow(a, 5)-pow(b, 5) == x:
            print(a, b)
            exit()
        b += 1
        a += 1

### FIXED CODE ###


x = int(input())

for i in range(100):
    for j in range(100):
        if pow(i, 5)+pow(j, 5) == x:
            print(i, -j)
            exit()


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


a = 0
for i in make_divisors(x):
    a = i
    b = 0
    while pow(a, 5)-pow(b, 5) <= x:
        if pow(a, 5)-pow(b, 5) == x:
            print(a, b)
            exit()
        b += 1
        a += 1
### BUGGY CODE ###

import sys

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]

"""
①BFSでゴールまで行けるかを試す
↓行けない
＃の位置を覚えておく（次に探索すべきqueに格納＆1つ目の数字として、1を入れておく。
↓
queの中身が全部行き止まりリストになったら（ソートして判断）、いったんループをやめて、count += 1
行き止まりリストの座標含む近傍の＃を全部.に変える。
↓
queの中身の各リストの1つ目の数字をすべて0に帰る。
↓
①に戻る
"""

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    maze[wallPointH][wallPointW]="."
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

que = [[0,0,0]]
count = 0
      
while que:
  #print(que)
  if que[0][0]==1:
    que.sort()
  if que[0][0]==1:
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだTrueがあるなら
    now = que.pop(0)
    nowH = now[1]
    nowW = now[2]
    if maze[nowH][nowW]=="#":#行き止まりの場合
      que.append([1,nowH,nowW])
      continue
    elif nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        que.append([0,nowH+1,nowW])
      if nowW+1 <= W-1:
        que.append([0,nowH,nowW+1])



### FIXED CODE ###

import sys
import heapq

H,W = map(int,input().split())
maze = [list(input()) for i in range(H)]

def removeWalls(wallPointH,wallPointW):
  if maze[wallPointH][wallPointW]=="#":
    changeTo = "."
  elif maze[wallPointH][wallPointW]=="1":
    changeTo = "0"
  if maze[wallPointH][wallPointW]=="#" or maze[wallPointH][wallPointW]=="1":
    maze[wallPointH][wallPointW]=changeTo
    if wallPointH+1 <= H-1:
      removeWalls(wallPointH+1,wallPointW)
    if wallPointW+1 <= W-1:
      removeWalls(wallPointH,wallPointW+1)

if maze[0][0]=="#":
  flag=1
else:
  flag=0
      
que = [[flag,0,0]]
heapq.heapify(que)
count = 0
      
while que:
  qu = heapq.heappop(que)
  if qu[0]==1:
    heapq.heappush(que, qu)
    count += 1
    for q in que:#いったん"#"の撤去作業を行う
      q[0]=0
      removeWalls(q[1],q[2])
  else:#queの中身にまだ進める場所があるなら
    nowH = qu[1]
    nowW = qu[2]
    if nowH==H-1 and nowW==W-1:#ゴールの場合
      print(count)
      sys.exit()
    else:#それ以外の場合
      #右近傍と下近傍、それぞれマップの中ならqueに格納。
      if nowH+1 <= H-1:
        if maze[nowH+1][nowW]=="#":
          maze[nowH+1][nowW]="1"
          heapq.heappush(que, [1,nowH+1,nowW])
        elif maze[nowH+1][nowW]==".":
          maze[nowH+1][nowW]="0"
          heapq.heappush(que, [0,nowH+1,nowW])
      if nowW+1 <= W-1:
        if maze[nowH][nowW+1]=="#":
          maze[nowH][nowW+1]="1"
          heapq.heappush(que, [1,nowH,nowW+1])
        elif maze[nowH][nowW+1]==".":
          maze[nowH][nowW+1]="0"
          heapq.heappush(que, [0,nowH,nowW+1])
### BUGGY CODE ###


a,b,x = map(int,input().split())
count = 0
for i in range(a,b+1):
    if i % x == 0:
        count += 1
print(count)

### FIXED CODE ###

a,b,x = map(int,input().split())
count = 0
count = b//x - (a-1)//x

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

import numpy
input_line=input().split(" ")
N,K=int(input_line[0]),int(input_line[1])
P=input().split(" ")

for i in range(N):
    P[i]=int(P[i])



new_total_box=[]
for j in range(N-K+1):
    total=0
    for i in range(j,K+j):
        total=total+P[i]
    new_total_box.append(total)
    
max_value = max(new_total_box)
max_index = new_total_box.index(max_value)


total_box=[]
total=0
for i in range(max_index,max_index+K):
    total=total+(P[i]+1)/2
    
print(total)
    

### FIXED CODE ###

input_line=input().split(" ")
N,K=int(input_line[0]),int(input_line[1])
P=input().split(" ")
cumsum=[0]
tol=0
for i in range(N):
    P[i]=(int(P[i])+1)/2
    tol=tol+P[i]
    cumsum.append(tol)
    
k_sum=[]

for i in range(N-K+1):
  k_sum.append(cumsum[i+K]-cumsum[i])  

ans=max(k_sum)
print(ans)
### BUGGY CODE ###

## C - Christmas Eve
import itertools
N, K = map(int, input().split())
rt = [max(x)-min(x) for x in list(itertools.combinations([int(input()) for i in range(N)], K))]
print(min(rt))

### FIXED CODE ###

## C - Christmas Eve
N, K = map(int, input().split())
H = sorted([int(input()) for i in range(N)])
rt = 10**9
for i in range(0,N-K+1):
    rt = H[K - 1 + i] - H[i] if rt > H[K - 1 + i] - H[i] else rt
print(rt)
### BUGGY CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
for i in range(q):
    b[i],c[i]=map(int,input().split())
    
#print(adic)    
for bi,ci in zip(b,c):
    if bi in adic and ci in adic:
        adic[ci]=adic[ci]+adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        adic[ci]=adic[bi]
        del adic[bi]
#    print(i,adic)
    asum=0
    for i,ad in adic.items():
        asum+=i*ad
    print(asum)

### FIXED CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
bc=[[0]*2 for i in range(q)]
for i in range(q):
    bc[i]=map(int,input().split())
    
asum=0
for i,ad in adic.items():
    asum+=i*ad
    
#print(adic)    
for bi,ci in bc:
    if bi in adic and ci in adic:
        asum-=bi*adic[bi]
        adic[ci]=adic[ci]+adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        asum-=bi*adic[bi]
        adic[ci]=adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
#    print(i,adic)
    print(asum)
### BUGGY CODE ###

import itertools
while True:
    n,s=map(int,input().split())
    if n==0 and s==0:
        break
    num=[i for i in range(0,s+1)]
    ans=0
    comb=itertools.combinations(num,n)
    for c in comb:
        if sum(c) == s:
            ans +=1
    print(ans)



### FIXED CODE ###

def counter(rest, n, acc, to):
  if rest == 0:return acc == to
  if n == 10:return 0 
  return counter(rest - 1, n + 1, acc + n , to) + counter(rest, n + 1, acc, to)
 
while True:
  n, s = map(int, input().split())
  if not n:
    break
  print(counter(n, 0, 0, s))
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)
total_list = [0 for _ in range(X*Y*Z)]
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) <= K:
                total_list[i*(Z*Y)+j*Z+k] = (a_list[i] + b_list[j] + c_list[k])
            else:
                break
total_list =  sorted(total_list, reverse = True)
for i in range(K):
    print(total_list[i])

### FIXED CODE ###

from heapq import heappush, heappop

# input
X,Y,Z,K = map(int, input().split())
a_list = [int(i) for i in input().split()]
b_list = [int(i) for i in input().split()]
c_list = [int(i) for i in input().split()]
a_list.sort(reverse = True)
b_list.sort(reverse = True)
c_list.sort(reverse = True)

#solve
hq = []
arg_hash = {}
val = a_list[0] + b_list[0] + c_list[0]
heappush(hq, (-val,0,0,0))

for i in range(K):
    ans, a, b, c = heappop(hq)
    print(-ans)

    arg_a = (a+1, b, c)
    arg_b = (a, b+1, c)
    arg_c = (a, b, c+1)

    if a < X-1 and arg_a not in arg_hash:
        arg_hash[arg_a] = 1
        heappush(hq, (-(a_list[a+1]+b_list[b]+c_list[c]),)+arg_a)
    if b < Y-1 and arg_b not in arg_hash:
        arg_hash[arg_b] = 1
        heappush(hq, (-(a_list[a]+b_list[b+1]+c_list[c]),)+arg_b)
    if c < Z-1 and arg_c not in arg_hash:
        arg_hash[arg_c] = 1
        heappush(hq, (-(a_list[a]+b_list[b]+c_list[c+1]),)+arg_c)
### BUGGY CODE ###

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

dp = [1000000000] * N
dp[0] = 0

for i in range(N - 1):
    for j in range(1, min(K + 1, N-i)):
        dp[i + j] = min(dp[i + j], abs(h[i + j] - h[i]) + dp[i])

print(dp[N - 1])

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())), dtype='int')
dp = np.ones(N, dtype='int') * 1000000000
dp[0] = 0

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

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

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    i2 = bisect.bisect_left(B, B[N - 1] / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = B[N - 1] - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = B[N - 1] / 2 - min_d
    max_half = B[N - 1] / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2)

    for i2 in range(i2_lo, i2_hi + 1):
        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (B[N - 1] + B[i2]) / 2, lo = i2 + 1)
        i1_lo = i1_hi = i1
        i3_lo = i3_hi = i3
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != B[N - 1] + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi + 1):
            for i3 in range(i3_lo, i3_hi + 1):
                P = B[i1]
                Q = B[i2] - B[i1]
                R = B[i3] - B[i2]
                S = B[N - 1] - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import bisect

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

    B = []
    t = 0
    for a in A:
        t += a
        B.append(t)

    T = B[N - 1]

    i2 = bisect.bisect_left(B, T / 2, lo = 1, hi = N - 2)
    i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
    i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)

    P = B[i1]
    Q = B[i2] - B[i1]
    R = B[i3] - B[i2]
    S = T - B[i3]

    min_d = max(P, Q, R, S) - min(P, Q, R, S)
    min_half = T / 2 - min_d
    max_half = T / 2 + min_d

    i2_lo = bisect.bisect_left(B, min_half, lo = 1, hi = N - 2)
    i2_hi = bisect.bisect_left(B, max_half, lo = i2_lo, hi = N - 2) + 1

    for i2 in range(i2_lo, i2_hi):
        if min_d * 2 < abs(T - 2 * B[i2]):
            continue

        i1 = bisect.bisect_left(B, B[i2] / 2, hi = i2)
        i3 = bisect.bisect_left(B, (T + B[i2]) / 2, lo = i2 + 1)
        i1_lo, i1_hi = i1, i1 + 1
        i3_lo, i3_hi = i3, i3 + 1
        if B[i1] * 2 != B[i2] and 0 < i1:
            i1_lo -= 1
        if B[i3] * 2 != T + B[i2] and i2 + 1 < i3:
            i3_lo -= 1

        for i1 in range(i1_lo, i1_hi):
            P = B[i1]
            Q = B[i2] - B[i1]
            for i3 in range(i3_lo, i3_hi):
                R = B[i3] - B[i2]
                S = T - B[i3]
                d = max(P, Q, R, S) - min(P, Q, R, S)
                if d < min_d:
                    min_d = d


    print(min_d)


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

#!/usr/bin/env python3

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[INF for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a,b =map(int,input().split())
        c = list(map(int,input().split()))

        # 開錠可能な箱をbitで表現する
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env pypy

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[INF for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a,b =map(int,input().split())
        c = list(map(int,input().split()))

        # 開錠可能な箱をbitで表現する
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

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

N = int(input())
A = [int(input()) for i in range(N)]
for i in range(N):
    print(max(max(A[0:i],A[i+1:])))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
tmp = max(A)
li = list(A)
li.sort(reverse=True)
if len(li)==1:
    tmp2 = li[0]
else:
    tmp2 = li[1]
for i in range(N):
    if A[i] != tmp:
        print(tmp)
    else:
        print(tmp2)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = str(input())
for _ in range(Q):
    l, r = map(int, input().split())
    print(S[l-1:r].count("AC"))

### FIXED CODE ###

N,Q = map(int, input().split())
S = str(input())
# N,Q=8,3
# S = "ACACTACG"
L = [0] * len(S) #ACのAの個数を保持
i = 0
sum_i = 0
while i < len(S)-1:
    if S[i] == "A":
        if S[i+1] == "C":
            L[i] = sum_i
            sum_i += 1
            L[i+1] = sum_i
            i += 2
        elif S[i+1] == "A":
            L[i] = sum_i
            i += 1
        else:
            L[i] = sum_i
            L[i+1] = sum_i
            i += 2
    else:
        L[i] = sum_i
        i += 1
L[len(S)-1] = sum_i
for _ in range(Q):
    l, r = map(int, input().split())
    print(L[r-1] - L[l-1])
### BUGGY CODE ###

from collections import Counter
N,M,Q = map(int,input().split())
T = [[0 for _ in range(N)] for _ in range(N)]
LR = []
for i in range(M):
  L,R = map(int, input().split())
  LR.append(L*1000+R)
LRD = Counter(LR)
for key in LRD:
  L,R=key//1000,key%1000
  v = LRD[key]
  for r in range(R-1,N):
    for l in range(L):
      T[l][r] += v
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][q-1])
print('\n'.join(map(str,ans)))


### FIXED CODE ###

N,M,Q = map(int,input().split())
T = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
  L,R = map(int, input().split())
  T[L][R] += 1
for l in range(1,N+1):
  for r in range(1,N+1):
    T[l][r] += T[l-1][r]+T[l][r-1]-T[l-1][r-1]
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][p-1]+T[q][q]-T[p-1][q]-T[q][p-1])
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import collections

def verify_anagrams(w1, w2):
    f = lambda y: "".join(sorted(map(lambda x: x.replace(' ', '').lower(), y)))
    return f(w1) == f(w2)

N = int(input())
S = []
for i in range(N):
    S.append(input())
    
cnt = 0
for i in range(N):
    for k in range(1,N-i):
        if verify_anagrams(S[i], S[i+k]):
            cnt += 1
print(cnt)

### FIXED CODE ###

N=int(input())
A=[]
D={}
count=0
for i in range(N):
    S=''.join(sorted(input()))
    A.append(S)

for s in A:
    if s in D:
        count+=D[s]
        D[s]+=1
    else:
        D[s]=1
print(count)
### BUGGY CODE ###

S = input()
T = input()
for i in range(len(S)):
    if S[i] != T[i]:
        
        motoT = [j for j in range(len(S)) if S[j] == T[i]]
        
        migawari = S[i]
        
        
        S = S.replace(S[i], T[i])
        
        
        for k in motoT:
            S = list(S)
            S[k] = migawari
            S = ''.join(S)

if S == T:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()

used = []
res  = []

for i in range(len(S)):
    if S[i] not in used:
        used.append(S[i])
    res.append(used.index(S[i]))

#print(used)
#print(res)
used = []
ret = []

for i in range(len(T)):
    if T[i] not in used:
        used.append(T[i])
    ret.append(used.index(T[i]))

if res == ret:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

s = input()
n = len(s)
pop = [1]*n

if n%2 == 1:
    step = n+1
else:
    step = n
    

for t in range(step):
    new_pop = [0]*n
    for i in range(n):
        if s[i] == "R":
            new_pop[i+1] += pop[i]
        else:
            new_pop[i-1] += pop[i]
    pop = new_pop
print(" ".join(map(str, pop)))

### FIXED CODE ###

import numpy as np
s = input()
n = len(s)

pop = [0]*n

lastR = 0
for i in range(n):
    if s[i] == "L":
        if (lastR - i)%2 == 1:
            pop[lastR+1] += 1
        else:
            pop[lastR] += 1
    else:
        lastR = i
            
lastL = n
for i in range(n-1, -1, -1):  
    if s[i] == "R":
        if (lastL - i)%2 == 1:
            pop[lastL-1] += 1
        else:
            pop[lastL] += 1
    else:
        lastL = i
        
print(" ".join(map(str, pop)))
### BUGGY CODE ###

import sys

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

N, K = na()
h = na()
 
S = [0] * N
S[0] = 0
 
for i in range(1, N):
    value = math.inf
    for step in range(1, K + 1):
        if i - step < 0:
            break
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
    S[i] = value
print(S[N - 1])

### FIXED CODE ###

from numba import jit
import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
 
@jit
def nya(N, K, h):
    S = [0] * N
    S[0] = 0
 
    for i in range(1, N):
        value = math.inf
        for step in range(1, K + 1):
            if i - step < 0:
                break
            value = min(value, S[i - step] + abs(h[i] - h[i - step]))
        S[i] = value
    return S[N-1]

print(nya(N, K, h))