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

inpl = lambda: list(map(int,input().split()))
N = int(input())
b = inpl()

def solution(chosen=[0]*N, n=0):
    if n == N:
        return []
    c = 0
    for i in range(N):
        if chosen[i] == 0 and b[i] == i + 1 - c:
            chosen[i] = 1
            s = solution(chosen, n+1)
            if s is None:
                chosen[i] = 0
            else:
                s.append(b[i])
                return s
        elif chosen[i] == 1:
            c += 1
    return None

ans = solution()
if ans is None:
    print(-1)
else:
    for i in range(N):
        print(ans[i])

### FIXED CODE ###

import numpy as np
inpl = lambda: list(map(int,input().split()))
N = int(input())
b = np.array(inpl(),dtype=np.int)

d = np.array(range(1,N+1),dtype=np.int) - b
if len(np.where(d < 0)[0]) > 0:
    print(-1)
    exit()

ans = np.empty(N,dtype=np.int)
for i in range(N):
    z = np.where(d == 0)[0]
    if len(z) == 0:
        print(-1)
        exit()
    else:
        k = z[-1]
        d[k] = -1
        for n in range(k+1,N):
            if d[n] > 0:
                d[n] -= 1
        ans[N-1-i] = b[k]

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
subs = []
for i in range(1,n):
    subs.append(h[i]-h[i-1])


sums = []

for i in range(len(subs)-1):
    sums.append(sum(subs[i:k+i-1]))


print(min(sums))


### FIXED CODE ###

import itertools
import math
import fractions
import functools
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
subs = []
for i in range(1,n):
    subs.append(h[i]-h[i-1])

amount = [0]*(n)
sums = 0
for i in range(0,len(subs)):
    sums += subs[i]
    amount[i+1] = sums


minimum = 10**10
for i in range(k-1,n):
    minimum = min(minimum,amount[i]-amount[i-k+1])

print(minimum)
### BUGGY CODE ###

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

dp = [10000000000]*(N)
dp[0]=0
for i in range(1,N):
  for j in range(0,K+1):
    if 0<=i-j:
      dp[i]=min(dp[i],dp[i-j]+abs(h[i-j]-h[i]))
 
print(dp[-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):
  dp=[0]*N
  for i in range(1,N):
    value=math.inf
    for j in range(1,K+1):
      if i-j<0:
        break
      value=min(value,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i]=value
  return(dp[N-1])
 
print(nya(N,K,h))
### BUGGY CODE ###

N = int(input())
An = input().split(' ')
ball_list = [0] * N
output_list = []
count = 0
for i in range(N):
    sum_amari = sum(ball_list[(N - i -1)::(N - i)])
    if sum_amari % 2 != int(An[N - i -1]): 
        ball_list[N - i -1] = 1
        output_list.insert(0,str(N - i))

print(len(output_list))
if len(output_list) > 0:
    print(' '.join(output_list))

### FIXED CODE ###

N = int(input())
An = input().split(' ')
ball_list = [0] * N
output_list = []
count = 0
for i in range(N):
    sum_amari = sum(ball_list[(N - i -1)::(N - i)])
    if sum_amari % 2 != int(An[N - i -1]): 
        ball_list[N - i -1] = 1
        output_list.append(str(N - i))
output_list.reverse()
print(len(output_list))
if len(output_list) > 0:
    print(' '.join(output_list))
### BUGGY CODE ###

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

    tmp = 1
    for i in range(K):
        tmp *= A[i]

    for i in range(N-K):
        t = tmp // A[i]
        t *= A[i+K]
        if t > tmp:
            print('Yes')
        else:
            print('No')
        tmp = t


if __name__ == "__main__":
    main()


### FIXED CODE ###

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

    for i in range(N-K):
        if A[i+K] > A[i]:
            print('Yes')
        else:
            print('No')


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

n,m = map(int,input().split())
a =list(map(int,input().split()))
b = sorted(a,reverse=True)


for i in range(m):
    max_b = b[0]
    b.pop(0)
    b.append(max_b//2)
    b = sorted(b,reverse = True)
print(sum(b))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq

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

# solve
ans = [-a for a in A]
heapq.heapify(ans)
for i in range(M):
    tmp = heapq.heappop(ans) * (-1) // 2
    heapq.heappush(ans, tmp * (-1))
ans = [-a for a in ans]

# output
print(sum(ans))
### BUGGY CODE ###

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

# print(N, S)
ans = N

f = S[0]
s = S[1:]

nw = 0
ne = 0

for w in s:
    if w != 'W':
        ne += 1

ans = nw+ne
for i in range(1, N):
    # skipflg = False
    f = S[0: i]
    l = S[i]
    s = S[i+1:]
    # print(i, f, l, s)
    # nw = f.count('W')
    # ne = s.count('E')
    # print(nw, ne)

    if S[i-1] != 'E':
        nw += 1

    if S[i] != 'W':
        ne -= 1
    # print(nw, ne)
    ans = min(ans, nw+ne)

print(ans)


### FIXED CODE ###

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

# print(N, S)
ans = N

f = S[0]
s = S[1:]

nw = 0
ne = 0

for w in s:
    if w != 'W':
        ne += 1

ans = nw+ne
for i in range(1, N):
    # skipflg = False
    # f = S[0: i]
    # l = S[i]
    # s = S[i+1:]
    # # print(i, f, l, s)
    # nw = f.count('W')
    # ne = s.count('E')
    # print(nw, ne)

    if S[i-1] != 'E':
        nw += 1

    if S[i] != 'W':
        ne -= 1
    # print(nw, ne)
    ans = min(ans, nw+ne)

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

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(b*k) == n:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = (int(i) for i in input().split())
ans = 0
for i in range(n//r+1):
    for j in range((n-(i*r))//g+1):
        k = (n-r*i-j*g)//b
        if r*i+j*g+abs(k*b) == n:
            ans += 1
print(ans)
### BUGGY CODE ###

import itertools

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


ans = 0

for x, y, z in itertools.combinations(l, 3):
    if x < y + z and y < z + x and z < x + y:
        ans += 1

print(ans)

### FIXED CODE ###

import bisect

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


ans = 0

l.sort()
# print(l)
for x in range(n):
    for y in range(x+1, n):
        t = bisect.bisect_left(l, max(l[x] - l[y], l[y] - l[x])+1, y+1)
        #print(l[x], l[y], max(l[x] - l[y], l[y] - l[x]), t, l[t])
        t2 = bisect.bisect_left(l, l[x] + l[y], y+1)
        #print(t2, l[t2] if t2 < n else None)
        #print(t2 - t)
        t3 = t2 - t
        if t3 > 0:
            ans += t3
print(ans)
### BUGGY CODE ###

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

r=s.count('R')
g=s.count('G')
b=s.count('B')

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    if s[i]==s[j]:
      continue
    for k in range(j,n):
      if j-i==k-j:
        if s[j]!=s[k] and s[k]!=s[i]:
          ng+=1
print(all-ng)

### FIXED CODE ###

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

#r=s.count('R')
#g=s.count('G')
#b=s.count('B')

r,g,b=0,0,0

for i in range(0,n):
  if s[i]=='R':
    r+=1
  elif s[i]=='G':
    g+=1
  else:
    b+=1

ng=0

all=r*g*b

#NGパターン数の洗い出し
for i in range(0,n-2):
  for j in range(i,n-1):
    if s[i]==s[j]:
      continue
    else:
      if j*2-i<=n-1:
#        print(i,j,j*2-i)
        if s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
          ng+=1
print(all-ng)
### BUGGY CODE ###

mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    XYP = []
    for _ in range(N):
        XYP.append(tuple(map(int, input().split())))

    ans = [float("inf")] * (N+1)
    for i in range(3**N):
        M = i
        L = []
        k = 0
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if M%3 == 0:
                L.append(XYP[j])
            elif M%3 == 1:
                k += 1
                Xline.append(XYP[j][0])
            else:
                k += 1
                Yline.append(XYP[j][1])
            M //= 3
        cost = 0
        for x, y, p in L:
            d = 10**6
            for xx in Xline:
                d = min(d, abs(x - xx))
            for yy in Yline:
                d = min(d, abs(y - yy))
            cost += d * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        x, y, p = map(int, input().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    dx = [[inf] * N for _ in range(1<<N)]
    dy = [[inf] * N for _ in range(1<<N)]
    for i in range(1 << N):
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(X[j])
                Yline.append(Y[j])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[i][j] = min(dx[i][j], abs(x - X[j]))
                dy[i][j] = min(dy[i][j], abs(y - Y[j]))

    ans = [inf] * (N+1)
    beki = [1<<j for j in range(N)]
    for i in range(3**(N-1)):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N-1):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki[j]
            else:
                k += 1
                iy += beki[j]
        for x in range(3):
            kk = k
            ix_ = ix
            iy_ = iy
            if x == 0:
                J.append(N-1)
            elif x == 1:
                kk += 1
                ix_ += beki[N-1]
            else:
                kk += 1
                iy_ += beki[N-1]
            cost = 0
            for j in J:
                p = P[j]
                cost += min(dx[ix_][j], dy[iy_][j]) * p
            ans[kk] = min(ans[kk], cost)
    for c in ans:
        print(c)


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

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
m = 62
d =[0]*m
ans = 0
for i in range(N):
    for j in range(m):
        if A[i]&(1<<j):
            ans += (1<<j)*(i-d[j])%mod
            d[j] += 1
        else:
            ans += (1<<j)*d[j]%mod
    ans %= mod
print(ans%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
m = 62
d =[0]*m
ans = 0
for i in range(N):
    for j in range(m):
        if A[i]&(1<<j):
            ans += (1<<j)*(i-d[j])%mod
            d[j] += 1
        else:
            ans += (1<<j)*d[j]%mod
    ans %= mod
print(ans%mod)
### BUGGY CODE ###

def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

def sub(d):
    #listを引数にとる
    sub_ls = []
    #print("")
    for i in range(n):
        for j in range(i+1, n):
            #print(d[i][j])
            sub_ls.append(d[i][j])
    sub_ls.sort()
    #print(sub_ls)
    k = 1
    cnt = 0
    ll = 1
    #print("")
    for i in range(len(sub_ls)):
        if k == sub_ls[i]:
            cnt+=1
        else:
            print(cnt)
            cnt = 1
            k+=1
            ll+=1
    if cnt != 0:
        print(cnt)
        ll+=1
    for i in range(ll, n):
        print(0)
    return

n,x, y = map(int,input().split())
d = [[float("inf")]*n for i in range(n)]

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
for i in range(n):
    d[i][i] = 0
d[x-1][y-1] = 1
d[y-1][x-1] = 1
#print(d,"\n")
a = warshall_floyd(d)
#print(warshall_floyd(d))
sub(a)


### FIXED CODE ###

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

ans = [0]*N

for i in range(1,N):
    for j in range(i+1,N+1):
        road = min(abs(j-i),abs(X-i)+abs(j-Y)+1,abs(Y-i)+abs(j-X)+1)
        ans[road] += 1

for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
H = [int(s) for s in input().split()]
l=0
for i in range(N):
  t_l=0
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      t_l = t_l + 1
    else:
      break
  if l < t_l:
    l = t_l
print(l)


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
l=0
t_l = 0
for i in range(N-1):
  if H[i] >= H[i+1]:
    t_l = t_l + 1
    if l < t_l:
      l = t_l
  else:
    t_l=0
print(l)
### BUGGY CODE ###

import sys
import numpy as np

N,K = map(int, sys.stdin.readline().split())

A = list(map(int, sys.stdin.readline().split()))

dp = np.zeros(K+1)

for k in range(0,K+1):
    win = False
    for i in A:
        if win:
            break
        elif k-i >= 0 and dp[k-i] == 0:
            dp[k] = 1
            win = True
            
if win:
    print('First')
else:
    print('Second')

### FIXED CODE ###

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

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

dp = [0] * (K+1)

for k in range(0,K+1):
    for i in A:
        if dp[k] == 0 and k-i >= 0 and dp[k-i] == 0:
            dp[k] = 1

            
if dp[k] == 1:
    print('First')
else:
    print('Second')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[-1]*W for _ in range(H)]
    from collections import deque
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j,0))

    answer = 0
    while queue:
        i,j,count = queue.popleft()

        if 0<=i<H and 0<=j<W and isVisited[i][j] == -1:
            isVisited[i][j] = count
            if count>answer:
                answer = count
            for ix,iy in [(0,1),(1,0),(-1,0),(0,-1)]:
               queue.append((i+ix,j+iy,count+1))
 
    print(answer)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def main():
    input = sys.stdin.readline  
    H,W = map(int,input().split())
    isVisited = [[False]*W for _ in range(H)]
    queue = deque()

    for i in range(H):
        st = input()
        for j in range(W):
            if st[j] == "#":
                queue.append((i,j))

    answer = 0
    a =  [(0,1),(1,0),(-1,0),(0,-1)]
    while True:
        nqueue = deque()
        while queue:
            i,j = queue.popleft()

            if not isVisited[i][j]:
                isVisited[i][j] = True
                for ix,iy in a:
                    if 0<=i+ix<H and 0<=j+iy<W:
                        nqueue.append((i+ix,j+iy))
        
        if nqueue:
            answer += 1
            queue = nqueue
        else:
            break
 
    print(max(answer-1,0))
    return

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

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 7 and Npower < 10:
    for i in range(0,10**6+10**5):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
    for i in range(N-10**6-10**5-10**4-10**3-10**2,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
print(max(maxi,0))

### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

N,K=map(int, input().split())
*h,=map(int,input().split())
INF=10**12

dp = [INF]*N
dp[0]=0

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

### FIXED CODE ###

N,K=map(int, input().split())
*h,=map(int,input().split())
INF=10**12

dp = [INF]*N
dp[0]=0

for i in range(1,N):
  if i <= K:
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,i+1)])
  else:
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,K+1)])
  
print(dp[-1])
### BUGGY CODE ###

n = int(input())
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
graph1 = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  graph[u-1][v-1] = w
  graph[v-1][u-1] = w
  graph1[u-1].append(v-1)
  graph1[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
def dfs(i,j):#(child, parent)
  for k in graph1[i]:
    if k ==j:
      continue
    if color[k] != -1:
      continue
    if graph[k][i] %2:
      color[k] = 1 -color[i]
    else:
      color[k] = color[i]
    dfs(k,i)
dfs(0,-1)

for i in range(n):
  print(color[i])



### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
d = {}
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  d[(u-1,v-1)] = w
  graph[u-1].append(v-1)
  graph[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
from collections import deque
queue =deque([0])

while queue:
  p = queue.popleft()
  color_p = color[p]
  for i in graph[p]:
    if color[i] != -1:
      continue
    else:
      if d[(min(i,p),max(i,p))] %2:
        color[i] = 1 - color_p
      else:
        color[i] = color_p
      queue.append(i)

for i in range(n):
  print(color[i])
### BUGGY CODE ###

s=input()
k=int(input())

sl=[]
l=len(s)
for i in range(l):
    for j in range(i+1):
        sl.append(s[j:i+1])
        
sl.sort()      
li=[]
for i in sl:
    if i not in li:
        li.append(i)

print(li[k-1])

### FIXED CODE ###

s=input()
k=int(input())

l=list(s)

import collections
c=collections.Counter(l)
li=c.most_common()
from operator import itemgetter
li.sort(key=itemgetter(0))

co=0
p=[]
for i in range(min(5,len(li))):
    for j in range(len(s)):
        if l[j]==li[i][0]:
            for e in range(min(len(s)-j,k)):
                co+=1
                p.append(s[j:j+e+1])

q=collections.Counter(p)
ans=q.most_common()
ans.sort(key=itemgetter(0))   

print(ans[k-1][0])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = 10**9 + 7

for i in range(n):
    for j in range(i+1,n):

        ans += a[i]*a[j]
print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = sum(a)**2
mod = 10**9 + 7

for i in range(n):
    ans -= a[i]**2
ans //= 2
print(ans%mod)
### BUGGY CODE ###

import collections

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = {}
cond_keys = []
for i in range(n):
  inputs = [int(x) for x in input().split()]
  if inputs[0] in cond_keys:
    conditions[inputs[0]].append(inputs[1])
  else:
    cond_keys.append(inputs[0])
    conditions[inputs[0]] = collections.deque([inputs[1]])

for day in conditions.keys():
  conditions[day] = sorted(conditions[day], reverse=True)

ans = 0
candidates = []
cand_len = 0
for reversed_day in range(1, m + 1):
  if reversed_day in cond_keys:
    candidates.append(conditions[reversed_day])
    cand_len += 1

  if cand_len == 0:
    continue

  cnt, maxval, maxkey = 0, 0, 0
  for cands in candidates:
    if cands[0] > maxval:
      maxval = cands[0]
      maxkey = cnt
    cnt += 1
  ans += candidates[maxkey].pop(0)
  if len(candidates[maxkey]) == 0:
    del candidates[maxkey]
    cand_len -= 1
print(ans)


### FIXED CODE ###


import collections
import heapq

inputs = [int(x) for x in input().split()]
n, m = inputs[0], inputs[1]
conditions = collections.deque([])
for i in range(n):
  conditions.append([int(x) for x in input().split()])

conditions = sorted(conditions)

cnt, ans = 0, 0
candidates = []
for reversed_day in range(1, m + 1):
  while cnt < len(conditions) and conditions[cnt][0] <= reversed_day:
    heapq.heappush(candidates, -conditions[cnt][1])
    cnt += 1

  if len(candidates) == 0:
    continue
  ans -= heapq.heappop(candidates)

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

import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    A, B, Q = map(int, input().split())
    S = [-10**100]
    T = [-10**100]
    for _ in range(A): S.append(int(input()))
    for _ in range(B): T.append(int(input()))
    S.append(10**100)
    T.append(10**100)

    for _ in range(Q):
        x = int(input())
        idx1 = bisect_left(S, x)
        idx2 = bisect_left(T, x)
        ans = 10 ** 100
        cand1 = (x - S[idx1 - 1]) + abs(S[idx1 - 1] - T[idx2 - 1])
        ans = min(ans, cand1)
        cand2 = (x - S[idx1 - 1]) + abs(S[idx1 - 1] - T[idx2])
        ans = min(ans, cand2)
        cand3 = (S[idx1] - x) + abs(S[idx1] - T[idx2 - 1])
        ans = min(ans, cand3)
        cand4 = (S[idx1] - x) + abs(S[idx1] - T[idx2])
        ans = min(ans, cand4)
        cand5 = (x - T[idx2 - 1]) + abs(T[idx2 - 1] - S[idx1 - 1])
        ans = min(ans, cand5)
        cand6 = (x - T[idx2 - 1]) + abs(T[idx2 - 1] - S[idx1])
        ans = min(ans, cand6)
        cand7 = (T[idx2] - x) + abs(T[idx2] - S[idx1 - 1])
        ans = min(ans, cand7)
        cand8 = (T[idx2] - x) + abs(T[idx2] - S[idx1])
        ans = min(ans, cand8)
        print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    A, B, Q = map(int, input().split())
    S = [-10**50]
    T = [-10**50]
    for _ in range(A): S.append(int(input()))
    for _ in range(B): T.append(int(input()))
    S.append(10**50)
    T.append(10**50)

    for _ in range(Q):
        x = int(input())
        idx1 = bisect_left(S, x)
        idx2 = bisect_left(T, x)
        ans = 10 ** 11
        cand1 = (x - S[idx1 - 1]) + abs(S[idx1 - 1] - T[idx2 - 1])
        ans = min(ans, cand1)
        cand2 = (x - S[idx1 - 1]) + (T[idx2] - S[idx1 - 1])
        ans = min(ans, cand2)
        cand3 = (S[idx1] - x) + (S[idx1] - T[idx2 - 1])
        ans = min(ans, cand3)
        cand4 = (S[idx1] - x) + abs(S[idx1] - T[idx2])
        ans = min(ans, cand4)
        cand5 = (x - T[idx2 - 1]) + abs(T[idx2 - 1] - S[idx1 - 1])
        ans = min(ans, cand5)
        cand6 = (x - T[idx2 - 1]) + (S[idx1] - T[idx2 - 1])
        ans = min(ans, cand6)
        cand7 = (T[idx2] - x) + (T[idx2] - S[idx1 - 1])
        ans = min(ans, cand7)
        cand8 = (T[idx2] - x) + abs(T[idx2] - S[idx1])
        ans = min(ans, cand8)
        print(ans)



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

N,K=map(int,input().split())
hn = list(map(int,input().split()))
#初期値
inf=float("inf")
dp=[inf]*(N+2)
dp[0], dp[1] = 0, abs(hn[1]-hn[0])

# DP
for i in range(2,N):
    kouho = []
    for j in range(1,K+1): kouho.append(dp[i-j]+abs(hn[i]-hn[i-j]))
    dp[i] = min(kouho)
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
H = np.array(list(map(int,input().split())))
 
dp = np.zeros(N, dtype=int)
for i in range(1,N):
    start = max(i-K,0)
    dp[i] = np.min(dp[start:i] + np.abs(H[i] - H[start:i]))
print(dp[-1])
### BUGGY CODE ###

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

def imos(n,a):
  imos_l=[0]*n
  for i in range(n):
    l=max(i-a[i],0)
    r=min(i+a[i],n-1)
    imos_l[l]+=1
    if (r+1)!=n:
      imos_l[r+1]-=1

  b=[0]
  for i in range(1,n+1):
    b.append(imos_l[i-1]+b[i-1])
  return b[1:]

for i in range(k):
  na=imos(n,a)
  if na==a:
    break
  a=na

print(*a)

### FIXED CODE ###

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

def imos(n,a):
  imos_l=[0 for i in range(n)]

  for i in range(n):
    x=i
    x_left=max(x-a[i],0)
    x_right=min(x+a[i],n-1)

    imos_l[x_left]+=1
    if (x_right+1)!=n:
      imos_l[x_right+1]-=1

  b=[0]
  for i in range(1,n+1):
    b.append(imos_l[i-1]+b[i-1])

  return(b[1:])

for i in range(k):
  a=imos(n,a)

  if a.count(n)==n:
    break

print(*a)