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

from collections import deque
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [[j == "#" for j in input()] for i in range(h)]
# for i in range(h):
#     a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


# スタート地点をqueueに追加
que = deque([(i,j) for i in range(h) for j in range(w) if a[i][j]])

loop = len(que)
count = 0

add = 0
while True:
    count += 1
    loop += add
    add = 0
    for i in range(loop):
        p = que.popleft()
        add -= 1
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and not a[ny][nx]:
                a[ny][nx] = True
                que.append((ny, nx))
                add += 1
    if not que:
        break

print(count - 1)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = list(input())

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que = deque()

white = h * w

# スタート地点をqueueに追加
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append([i, j])
            white -= 1

count = 0
while 1:
    if white == 0:
        break
    count += 1
    loop = len(que)
    for i in range(loop):
        p = que.popleft()
        for j in range(4):
            ny = p[0] + dy[j]
            nx = p[1] + dx[j]
            if nx < w and nx >= 0 and ny < h and ny >= 0 and a[ny][nx] == ".":
                a[ny][nx] = "#"
                white -= 1
                que.append([ny, nx])


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

"""
T E S T
"""

from collections import Counter, deque

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

cnt_a = Counter(A)
cnt_b = Counter(B)

cnt_ab = cnt_a + cnt_b

for i in cnt_ab.values():
    if i > N:
        print("No")
        exit()


print("Yes")
dq_a = deque(A)
dq_b = deque(B)

ans = []

# b.rotate(n // 2)

while dq_a:
    if dq_a[0] != dq_b[0]:
        dq_a.popleft()
        p = dq_b.popleft()
        ans.append(p)
        # ans.append(b.popleft())
    else:
        dq_b.rotate()
print(*ans)


### FIXED CODE ###

"""
T E S T
"""

from collections import Counter, deque

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

cnt_a = Counter(A)
cnt_b = Counter(B)

cnt_ab = cnt_a + cnt_b

for i in cnt_ab.values():
    if i > N:
        print("No")
        exit()


print("Yes")
dq_a = deque(A)
dq_b = deque(B)

ans = []

dq_b.rotate(N // 2)

while dq_a:
    if dq_a[0] != dq_b[0]:
        dq_a.popleft()
        p = dq_b.popleft()
        ans.append(p)
        # ans.append(b.popleft())
    else:
        dq_b.rotate()
print(*ans)
### BUGGY CODE ###

def check() -> int:
    n = int(input())
    n_l = list(map(int, input().split()))

    VORDER = 10 ** 18
    ans = 1

    for i in n_l:
        if 0 in n_l:
            ans = 0
            break
        ans = i * ans
        if ans > VORDER:
            ans = -1
            break

    return ans


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

### FIXED CODE ###

def check() -> int:
    n = int(input())
    n_l = list(map(int, input().split()))

    VORDER = 10 ** 18
    ans = 1

    if 0 in n_l:
        ans = 0
    else:
        for i in n_l:
            ans = i * ans
            if ans > VORDER:
                ans = -1
                break
    return ans


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

n = int(input())
l = list(map(int,input().split()))
s = 0
for x in range(n-1):
  s+=l[x]*(sum(l[x+1:]))
print(s%1000000007)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
s = 0
s1 = sum(l)
a = 0
for x in range(n-1):
  s+=(l[x]*(s1-l[x]-a))
  a+=l[x]
print(s%1000000007)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
  r,l=map(int,input().split())
  ans=0
  for j in range(r-1,l-1):
    if s[j]=='A' and s[j+1]=='C':
      ans+=1
  print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
lr=[list(map(int,input().split())) for i in range(q)]
data=[0]*(n+1)
if s[0]=='A' and s[1]=='C':
  data[1]=1
for i in range(1,n-1):
  if s[i]=='A' and s[i+1]=='C':
    data[i+1]+=1
  data[i+1]+=data[i]
data[n]=data[n-1]
for i in range(q):
  print(data[lr[i][1]-1]-data[lr[i][0]-1])
### BUGGY CODE ###

N = int(input())
A = list((int(x) for x in input().split()))
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    ans += A[i]*A[j] % (10**9+7)
print(ans % (10**9+7))

### FIXED CODE ###

N = int(input())
b = 10**9+7
A = list((int(x) for x in input().split()))
sum = 0
for a in A:
  sum += a
ans = 0
for i in range(N-1):
  sum -= A[i]
  ans += A[i]*sum
print(ans % b)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]

def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        

def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        

ans = 0

for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
            if ans == H + W -1:
                print (ans)
                sys.exit()
print (ans)


### FIXED CODE ###

#上下方向の探索と左右方向の探索をまとめる
#まず表を完成させる-->全マスの探索
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[0] * (W+2) for i in range(H+2)]
lst_shita = [[0] * (W+2) for i in range(H+2)]
lst_migi = [[0] * (W+2) for i in range(H+2)]
lst_hidari = [[0] * (W+2) for i in range(H+2)]

for i in range(1, H+1):
    for j in range(1, W+1):
        lst_hidari[i][j] = 0 if lst[i][j] == '#' else 1 + lst_hidari[i][j-1]
    for j in range(W, 0, -1):
        lst_migi[i][j] = 0 if lst[i][j] == '#' else 1 + lst_migi[i][j+1]

for j in range(1, W+1):
    for i in range(1, H+1):
        lst_ue[i][j] = 0 if lst[i][j] == '#' else 1 + lst_ue[i-1][j]
    for i in range(H+1, 0, -1):
        lst_shita[i][j] = 0 if lst[i][j] == '#' else 1 + lst_shita[i+1][j]

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        ans = max(ans, lst_ue[i][j]+lst_shita[i][j]+lst_migi[i][j]+lst_hidari[i][j]-3)

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

# -*- coding: utf-8 -*-

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

A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in A:
        s=A.index(a)
        break
    else:
        A.append(a)

if len(A)==N:
    ans=sum(A)
else:
    ans=0
    l=len(A)-s

    ans+=sum(A[:s])
    S=sum(A[s:])
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    ans+=sum(A[s:(s+K)])
    


print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

A=[0]*10**5
A[0]=X
D=dict()
#A=[X]
s=N
for i in range(1,N):
    a=A[i-1]**2%M
    if a in D:
        s=A.index(a)
        break
    else:
        #A.append(a)
        A[i]=a
        D[a]=0

if s==N:
    ans=sum(A)
else:
    A=A[:i]
    Z=[0]*(len(A)+1)
    for i in range(1,len(A)+1):
        Z[i]=Z[i-1]+A[i-1]  

    ans=0
    l=len(A)-s
    #ans+=sum(A[:s])
    ans+=Z[s]
    #S=sum(A[s:])
    S=Z[len(A)]-Z[s]
    T=(N-s)//l
    ans+=T*S
    K=N-s-l*T
    #ans+=sum(A[s:(s+K)])
    ans+=Z[s+K]-Z[s]


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

N = int(input())

counter = []

for i in range(N):
    si = input()
    if si not in counter:
        counter.append(si)

print(len(counter))


### FIXED CODE ###

N = int(input())

counter = set([])

for i in range(N):
    si = input()
    if si not in counter:
        counter.add(si)

print(len(counter))
### BUGGY CODE ###

import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

memo = {(0,0,0): 0}

def calc(i1, i2, i3):
  i = (i1,i2,i3)
  if i in memo:
    return memo[i]

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  memo[(i1,i2,i3)] = ex
  return ex

print(calc(n1, n2, n3))


### FIXED CODE ###

import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

dp = [[0]*(n2+n3+1) for _ in range(n3+1)]
dp[n3][n2] = 1.0
ans = 0

for i in range(s, 0, -1):
  dp2 = [[0]*(n2+n3+1) for _ in range(n3+1)]
  for i3 in range(n3, -1, -1):
    for i2 in range(min(n2+n3, (i-i3*3)//2), -1, -1):
      i1 = i-i3*3-i2*2
      i0 = n-i1-i2-i3
      if i2 < 0 or i1 < 0 or i0 < 0: continue
      e0 = n/(i1+i2+i3)
      dp2[i3][i2] += dp[i3][i2] * i1/(i1+i2+i3)
      ans += dp[i3][i2] * e0*(i1/(i1+i2+i3))
      if i2 > 0:
        dp2[i3][i2-1] += dp[i3][i2] * i2/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i2/(i1+i2+i3))
      if i3 > 0 and i2 < n2+n3:
        dp2[i3-1][i2+1] += dp[i3][i2] * i3/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i3/(i1+i2+i3))
  dp = dp2

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

num = int(input())
wr = str(input())

i_counts = []
r_num = wr.count("R")

if r_num == 0:
  ans = 0
else:

  for i in range(r_num):
    w_counts = 0
    r_counts = 0
    for j in range(num):
      if i > j and wr[j] == "W":
        w_counts += 1
      elif i < j and wr[j] == "R":
        r_counts += 1
    i_count = max(w_counts, r_counts)
    i_counts.append(i_count)

  ans = min(i_counts)

print(ans)

### FIXED CODE ###

num = int(input())
wr = str(input())

r_num = wr.count("R")
i_counts = [r_num]
rw_count = r_num
wr_count = 0
for i in range(num):
  if wr[i] == "W":
    wr_count += 1
  else:
    rw_count -= 1
  i_count = max(wr_count, rw_count)
  i_counts.append(i_count)

ans = min(i_counts)

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

N, M = [int(x) for x in input().split()]

A = [[] for i in range(M)]

for i in range(N):
	t1, t2 = [int(x) for x in input().split()]
	if t1-1 <= M-1:
		A[t1-1].append(t2)


ans = 0
for i in range(M):
	t = 0
	idx = -1
	for j in range(i+1):
		if A[j] != []:
			if max(A[j]) >= t:
				idx = j
				t = max(A[j])
	if idx!=-1:
		ans += t
		A[idx].remove(t)


print(ans)


### FIXED CODE ###

import heapq

N,M=map(int,input().split())
d={}
for i in range(M):d[i]=[0]
for i in range(N):
    a,b=map(int,input().split())
    if 0<=M-a:
        d[M-a].append(b)

hq=[]
ans=0
for i in range(M)[::-1]:
    [heapq.heappush(hq,-j) for j in d[i]]
    ans-=heapq.heappop(hq)
print(ans)
### BUGGY CODE ###

from numba import njit

N, K, *A = map(int, open(0).read().split())

@njit(cache=True)
def solve(A):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    for i in range(N):
        B[i + 1] += B[i]
    return B

for _ in range(min(K, 41)):
    A = solve(A)

print(*A[:-1])

### FIXED CODE ###

from itertools import accumulate

N, K, *A = map(int, open(0).read().split())

for _ in range(min(K, 41)):
    B = [0] * (N + 1)
    for x, d in enumerate(A):
        B[max(0, x - d)] += 1
        B[min(N, x + d + 1)] -= 1
    A = list(accumulate(B))

print(*A[:-1])
### BUGGY CODE ###

#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
table=list(range(M))
for i in range(M):
    table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rireki=list()
rireki.append(start)
ss=0
for j in range(1,N):
    if table[start] in rireki:
        ss=rireki.index(table[start])
        break
    else:
        rireki.append(table[start])
        start=table[start]
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)

### FIXED CODE ###

#import sys
#print(sys.maxsize)
N,X,M=map(int,input().split())
#table=list(range(M))
#for i in range(M):
 #   table[i]=((table[i]%M)**2)%M
#print(table[471])
start=X%M
rset=set()
rireki=list()
rset.add(start)
rireki.append(start)
ss=0
for j in range(1,M+1):
    start=(start**2)%M
    if start in rset:
        ss=rireki.index(start)
        break
    else:
        rireki.append(start)
        rset.add(start)
nn=len(rireki)
rep=(N-ss)//(nn-ss)
nokori=N-ss-rep*(nn-ss)
loop=rireki[ss:]
#print(nn)
#print(rep)
#print(sum(loop))
#print(ss)
#print(nokori+rep*(nn-ss)+ss)
if 0 in rireki:
    goukei=sum(rireki)
else:
    goukei=rep*sum(loop)+sum(rireki[:ss])+sum(loop[:nokori])
print(goukei)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Summer Vacation
https://atcoder.jp/contests/abc137/tasks/abc137_d

"""
import sys


from heapq import heapify, heappop
from bisect import bisect_left

def solve(N, M, jobs):
    days = [d for d in range(1, M+1)]
    heapify(jobs)
    ans = 0
    while jobs:
        B, A = heappop(jobs)
        i = bisect_left(days, -A)
        if i != len(days):
            days.pop(i)
            ans -= B
    return ans


def main(args):
    N, M = map(int, input().split())
    jobs = []
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append([-B, -A])
    ans = solve(N, M, jobs)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Summer Vacation
https://atcoder.jp/contests/abc137/tasks/abc137_d

"""
import sys


from heapq import heapify, heappop, heappush

def solve(N, M, jobs):
    heapify(jobs)
    availables = []
    ans = 0
    for day in range(1, M+1):
        while jobs and jobs[0][0] <= day:
            A, B = heappop(jobs)
            heappush(availables, (-B))
        if availables:
            ans -= heappop(availables)
    return ans


def main(args):
    N, M = map(int, input().split())
    jobs = []
    for _ in range(N):
        A, B = map(int, input().split())
        jobs.append((A, B))
    ans = solve(N, M, jobs)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

k = int(input())
ans = 0
def gcd(a,b):
    if a % b == 0:
        return b
    c = a % b
    return gcd(b,c)

for l in range(1,k+1):
    for m in range(1,k+1):
        for n in range(1,k+1):
            tmp = gcd(l,n)
            ans += gcd(tmp,m)

print(ans)

### FIXED CODE ###

k = int(input())
ans = 0
def gcd(a,b):
    if a % b == 0:
        return b
    c = a % b
    return gcd(b,c)

for l in range(1,k+1):
    for m in range(l,k+1):
        for n in range(m,k+1):
            tmp1 = gcd(l,n)
            tmp2= gcd(tmp1,m)
            if (l==m==n):
                ans+=tmp2
            elif(l==m or m==n):
                ans+= 3*tmp2
            else:
                ans += 6*tmp2


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

import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    res = 0
    p = 0

    for i in range(1,30):
        p += 1<<(i-1)
        tank = []
        for eb in b:
            tank.append(eb&p)
        tank.sort()

        cnt = 0
        
        
        q2 = p+1
        q1 = q2>>1
        q3 = q2<<1

        for elt in a:
            e = elt&p

            cnt += bisect.bisect_left(tank, q2-e ) - bisect.bisect_left(tank, q1-e)
            cnt += bisect.bisect_left(tank, q3-e ) - bisect.bisect_left(tank, 3*q1-e)
        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    res = 0
    p = 0

    for i in range(1,30):
        p += 1<<(i-1)
        A = []
        B = []

        for j in range(n):
            A.append(a[j]&p)
            B.append(b[j]&p)
        A.sort()
        B.sort()

        cnt = 0

        q2 = p+1
        q1 = q2>>1
        q3 = q2<<1

        k1,k2,k3,k4 = 0,0,0,0

        for j in range(n-1,-1,-1):
            while k1 < n and A[j]+B[k1] < q1:
                k1 += 1
            while k2 < n and A[j]+B[k2] < q2:
                k2 += 1
            while k3 < n and A[j]+B[k3] < 3*q1:
                k3 += 1
            while k4 < n and A[j]+B[k4] < q3:
                k4 += 1
            cnt += k4 + k2 - k1 - k3

        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


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

N = int(input())

s = [sorted(list(input())) for i in range(N)]
count = []
while len(s)>0:
    c = 0
    cc = []
    for i in range(0,len(s)):
        if s[0]==s[i]:
            c += 1
            cc.append(i)
    count.append(c)
    if len(cc)==0: cc.append(0)
    for i in cc[::-1]:
        del s[i]

ans = 0

for i in count:
    ans += (1/2)*i*(i-1)

print(int(ans))


### FIXED CODE ###

import collections
N = int(input())

s = [sorted(list(input())) for i in range(N)]

for i in range(N):
    s[i] = ''.join(s[i])

ans = 0

c = collections.Counter(s)
for v in c.values():
    ans += (1/2) * v * (v-1)

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

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    rgb[(c > 'G') + (c > 'B')].append(i)

exclude = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            exclude += 1
        if jj + d < n and jj + d in rgb[2]:
            exclude += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            exclude += 1

summ = len(rgb[0]) * len(rgb[1]) * len(rgb[2])
print(summ - exclude)

### FIXED CODE ###

n = int(input())
s = input()

rgb = [[], [], []]

for i, c in enumerate(s):
    rgb[(c > 'G') + (c > 'B')].append(i)

exclude = 0
for i in rgb[0]:
    for j in rgb[1]:
        ii = min(i, j)
        jj = max(i, j)
        d = jj - ii
        if ii - d >= 0 and ii - d in rgb[2]:
            exclude += 1
        if jj + d < n and jj + d in rgb[2]:
            exclude += 1
        if not d % 2 and ii + d // 2 in rgb[2]:
            exclude += 1

summ = len(rgb[0]) * len(rgb[1]) * len(rgb[2])
print(summ - exclude)
### BUGGY CODE ###

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)

n = k = ar = dp = 0

def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,min(n,x+k+1)):
		m = min(m,abs(ar[x]-ar[i])+solve(i))
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	global n,ar,k,dp
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
visited[f] = True
cnt = 0
while True:
    cnt += 1
    t = a[f]
    if t == 1:
        flg = True
        break
    if visited[t]:
        flg = False
        break
    f = t
print(cnt) if flg else print(-1)

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
    a.append(int(input()) - 1)

visited = [False] * n
f = 0
visited[f] = True
cnt = 0
while True:
    cnt += 1
    t = a[f]
    if t == 1:
        flg = True
        break
    if visited[t]:
        flg = False
        break
    visited[t] = True
    f = t
print(cnt) if flg else print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
if n < m:
    distance = []
    for i in range(m-1):
        distance.append(x[i + 1] - x[i])
    for _ in range(n - 1):
        distance.remove(max(distance))
    print(sum(distance))
else:
    print(0)

### FIXED CODE ###

n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
if n < m:
    distance = []
    for i in range(m-1):
        distance.append(x[i + 1] - x[i])
    distance.sort()
    print(sum(distance[0:m-n]))
else:
    print(0)
### BUGGY CODE ###

from math import factorial

MOD = 10 ** 9 + 7

def mult(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def solve():
  N = int(input())
  S = input()
  if S[0] != 'B' or S[-1] != 'B': return 0

  D = 'L'
  for i in range(1, N * 2):
    d = D[-1]
    if S[i] != S[i - 1]: D += d
    else: D += 'L' if d == 'R' else 'R'

  if D.count('L') != D.count('R'): return 0

  C = 1
  c = 0
  for d in D:
    if d == 'L': c += 1
    else:
      C *= c
      c -= 1
      if c < 0: return 0

  return mult(factorial(N), C)

print(solve())

### FIXED CODE ###

MOD = 10 ** 9 + 7

def solve():
  N = int(input())
  S = [s == 'W' for s in input()] # W: True, B: False
  if S[0] or S[2 * N - 1]: return 0

  ans = 1
  cnt = 1
  d = True # L: True, R: False
  for i in range(1, N * 2):
    if S[i] == S[i - 1]: d = not d
    if d: cnt += 1
    else:
      ans = (ans * cnt) % MOD
      cnt -= 1

  for i in range(1, N + 1): ans = (ans * i) % MOD

  return ans if cnt == 0 else 0

print(solve())
### BUGGY CODE ###

import numpy as np

MOD = 10**9+7
S = str(input())
check = []
ans = 0
plo = np.array([1]+[0] * 12)
N = len(S)
for i in range(N):
    if S[N - 1 - i] == '?':
        temp = np.array([0] * 13)
        for k in range(10):
            j = (k * 10 ** i) % 13
            temp += np.r_[plo[-j:],plo[:-j]]
        plo = temp % MOD
    else:
        j = (int(S[N - 1 - i]) * 10 ** i) % 13
        plo = np.r_[plo[-j:],plo[:-j]]
print(plo[5])

### FIXED CODE ###

from copy import copy

MOD = 10**9 + 7
s = input()
count = [0 for _ in range(13)]
count[0] = 1
for i in range(len(s)):
    new = [0 for _ in range(13)]
    for m in range(13):
        new[(m * 10) % 13] = count[m]
    count = new
    if s[i] != "?":
        div = int(s[i])
        count = count[-div:] +  count[:-div]
    else:
        new = [0 for _ in range(13)]
        pre = sum(count[:3])
        SUM = sum(count) % MOD
        for j in range(13):
            pre += count[(j+3) % 13]
            pre -= count[j % 13]
            new[j] = (SUM - pre) % MOD
        count = new
print(count[5])