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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import numpy as np
from operator import itemgetter

n = int(input())
s = []

# for i in range(n):
#     s.append(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

# for i in s:
#     if i not in buf:
#         buf.append(i)
#         cnt.append(0)
#     cnt[buf.index(i)] += 1

# ans = np.where(cnt == np.max(cnt))[0].tolist()
ans2 = np.array(buf)[np.array(cnt) == max(cnt)]

# ans = [i for i, x in enumerate(cnt) if x == max(cnt)]

# ans2 = [buf[i] for i in range(len(buf)) if i in ans]


ans3 = np.sort(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

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

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

from itertools import combinations

from collections import deque


def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1

def count_unreachable(a):
    if len(a) == 0:
        return 0
    ans = 0
    ls = list(map(len, a))
    for l1, l2 in combinations(ls, 2):
        ans += l1 * l2
    return ans


n, m = map(int, input().split())
edges = []
node_group = [[n] for n in range(1, n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

ans = deque()
ans.append(n * (n - 1) // 2)

for _ in range(m - 1):
    a, b = edges.pop()
    ia = find_index_by_value(node_group, a)
    ib = find_index_by_value(node_group, b)
    if ia != ib:
        node_group[ia].extend(node_group[ib])
        node_group.pop(ib)
    c = count_unreachable(node_group)
    ans.appendleft(c)

for _ in range(len(ans)):
    print(ans.popleft())




### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())
### BUGGY CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x % y # x,yの大小が逆でも、入れ替わるので、OK
    return x

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

if n == 2:
    print(max(a))

elif n>=3:
    l = [-1] * n
    r = [-1] * n
    l[0] = a[0]  #一番左を左に挿入
    r[-1] = a[-1] #一番右を右に挿入
# print(l)
# print(r)

    for i in range(1, n): #左から最大公約数をn-1回計算していく
        l[i] = gcd(l[i-1], a[i]) # l[0]とa[1]の最大公約数をl[1]に挿入⇒
        # l[1]とa[2]の最大公約数をl[2]に挿入。隣同士素があったら、それ以降右側全て1
        for i in range(n-2, -1, -1): #右から最大公約数を計算していく
            r[i] = gcd(r[i+1], a[i]) # r[n-1]とa[n-2]の最大公約数をr[n-2]に挿入

        # print("l",l) # lはn-1桁のlist
        # print("r",r)

        ans = max(r[1], l[-2]) # rの左から2番目とlの右から2番目の大きい方を、ansに挿入.
        # 右端、左端は、最大公約数ではないため。(元々の数列)

        for i in range(1, n-1): #両端を切り取った中で、lは右側に寄せて、rは左側に寄せているので、
            g = gcd(l[i-1], r[i+1]) #
            ans = max(ans, g)
            # print(i, g, ans)
    print(ans)

### FIXED CODE ###

def gcd(x, y):
    while y!=0:
        x, y = y, x % y # x,yの大小が逆でも、入れ替わるので、OK
    return x

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

if n == 2:
    print(max(a))

elif n>=3:
    l = [-1] * n
    r = [-1] * n
    l[0] = a[0]  #一番左を左に挿入
    r[-1] = a[-1] #一番右を右に挿入
# print(l)
# print(r)

    for i in range(1, n): #左から最大公約数をn-1回計算していく
        l[i] = gcd(l[i-1], a[i]) # l[0]とa[1]の最大公約数をl[1]に挿入⇒
        # l[1]とa[2]の最大公約数をl[2]に挿入。隣同士素があったら、それ以降右側全て1
    for i in range(n-2, -1, -1): #右から最大公約数を計算していく
        r[i] = gcd(r[i+1], a[i]) # r[n-1]とa[n-2]の最大公約数をr[n-2]に挿入

        # print("l",l) # lはn-1桁のlist
        # print("r",r)

    ans = max(r[1], l[-2]) # rの左から2番目とlの右から2番目の大きい方を、ansに挿入.
        # 右端、左端は、最大公約数ではないため。(元々の数列)

    for i in range(1, n-1): #両端を切り取った中で、lは右側に寄せて、rは左側に寄せているので、
        g = gcd(l[i-1], r[i+1]) #
        ans = max(ans, g)
        # print(i, g, ans)
    print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
s = [str(input()) for i in range(n)]
m = 0
for i in itertools.combinations(s,2):
    num = 0
    for h in range(10):
        if i[1].count(i[0][h]) == i[0].count(i[0][h]):
            num += 1
    if num == 10:
        m += 1
print(m)

### FIXED CODE ###

from collections import Counter
n = int(input())
s = []
for i in range(n):
    s1 = ''.join(sorted(input()))
    s.append(s1)
s = Counter(s).most_common()
num = 0
for i,h in s:
    num += (h*(h-1))//2
print(num)
### BUGGY CODE ###

H, W, M = list(map(int, input().split())) 
hw = [list(map(int, input().split())) for _ in range(M)]

LH = [0] * H
LW = [0] * W

R = {}
for i in range(M):
  h = hw[i][0] - 1
  w = hw[i][1] - 1
  LH[h] += 1
  LW[w] += 1
  if h in R:
    R[h][w] = 1
  else:
    R[h] = {}
    R[h][w] = 1

mah = max(LH)
maw = max(LW)

ans = mah + maw
for i in range(H):
  if LH[i] != mah: continue
  for j in range(W):
    if LW[j] != maw: continue
    if i not in R:
      break
    if j not in R[i]:
      break
  else:
    continue
  break
else:
  print(ans - 1)
  exit()

print(ans)


### FIXED CODE ###

H, W, M = list(map(int, input().split())) 
hw = [list(map(int, input().split())) for _ in range(M)]

LH = [0] * H
LW = [0] * W

R = {}
for i in range(M):
  h = hw[i][0] - 1
  w = hw[i][1] - 1
  LH[h] += 1
  LW[w] += 1
  if h in R:
    R[h][w] = 1
  else:
    R[h] = {}
    R[h][w] = 1

mah = max(LH)
maw = max(LW)
DH = []
DW = []

for i in range(H):
  if LH[i] == mah:
    DH.append(i)
for i in range(W):
  if LW[i] == maw:
    DW.append(i)

ans = mah + maw
for i in DH:
  if LH[i] != mah: continue
  for j in DW:
    if LW[j] != maw: continue
    if i not in R:
      break
    if j not in R[i]:
      break
  else:
    continue
  break
else:
  print(ans - 1)
  exit()

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

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

# K個連続した区間での最大が期待値の最大として、SでK個連続した最大値を探す。
maxSKsum=0
startSindex=0

#1.大きい区間を探す
for i in range(len(S)):  #ここがrange(len(S)-K)ではダメっぽいのがわからない・・・
    tempSKsum=sum(S[i:i+K])
    if maxSKsum<tempSKsum:
        maxSKsum=tempSKsum
        startSindex=i
    else:
        pass

#2.1で探した大きい区間の計算をする。
EV=0
for s in range(K):
    tempEV=S[startSindex+s]*(S[startSindex+s]+1)/2/S[startSindex+s]
    EV+=tempEV

print(EV)

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

nk = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = 0

zeros = [0] * nk[1]

seq4search = zeros + p

for i in range(nk[1], nk[0] + nk[1]):
    seq4search[i] = (seq4search[i] + 1) / 2
    if ans < sum(seq4search[i - nk[1] + 1:i + 1]):
        ans = sum(seq4search[i - nk[1] + 1:i + 1])

print(ans)

### FIXED CODE ###

nk = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = [0] * (nk[0] + nk[1])
 
zeros = [0] * nk[1]
 
seq4search = zeros + p
 
for i in range(nk[1], nk[0] + nk[1]):
    seq4search[i] = (seq4search[i] + 1) / 2
    ans[i] = ans[i-1] + seq4search[i] - seq4search[i - nk[1]] 
 
print(max(ans))
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

S = [list(input().strip()) for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        ny, nx = y+h, x+w
        if 0 <= ny and ny < H and 0 <= nx and nx < W:
            if S[ny][nx] == "." and worp < worps[ny][nx]:
                worps[ny][nx] = worp
                q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.appendleft([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1
d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
S = [input() for _ in range(H)]

worps = [[float('inf')]*W for _ in range(H)]
q = deque([[cy, cx]])

worps[cy][cx] = 0
while q:
    y, x = q.popleft()
    worp = worps[y][x]

    for h, w in d:
        ny, nx = y+h, x+w
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == "." and worp < worps[ny][nx]:
            worps[ny][nx] = worp
            q.appendleft([ny, nx])

    worp += 1
    for h in range(-2+y, 3+y):
        for w in range(-2+x, 3+x):
            if 0 <= h < H and 0 <= w < W and S[h][w] == "." and worp < worps[h][w]:
                worps[h][w] = worp
                q.append([h, w])

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

#!/usr/bin/env python
"""AtCoder nomura 2020: B - Postdocs - 
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_b
"""

__author__ = 'bugttle <bugttle@gmail.com>'

def calc(t):
    d = list(t).count('D')
    pd = list(t.replace('PD', '?')).count('?')
    return d + pd

def main():
    T = input()

    max_t = ''
    max_count = 0
    n = list(T).count('?')
    for i in range(2 ** n):
        t = T
        for j in range(n):
            if ((i >> j) & 1):
                t = t.replace('?', 'D', 1)
            else:
                t = t.replace('?', 'P', 1)
        point = calc(t)
        if max_count < point:
            max_count = point
            max_t = t

    print(max_t)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
"""AtCoder nomura 2020: B - Postdocs - 
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_b
"""

__author__ = 'bugttle <bugttle@gmail.com>'

def main():
    T = input()

    # S = T.replace('??', 'DD').replace('?D', 'DD').replace('D?', 'DD').replace('P?', 'PD').replace('?P', 'DP')
    S = T.replace('?', 'D')
    print(S)


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

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

ans = [sum(cnt[x:y]) for x, y in zip(range(0, N-K+1), range(K, N+1))]
print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
cnt = [int(x) * 0.5 + 0.5 for x in input().split()]

add = [0]
for i in cnt:
    add.append(add[-1]+i)

ans = [add[i+K]-add[i] for i in range(N-K+1)]

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

N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2))
    # N = -(N - N % 2) 
print("".join(list(reversed(a))))

### FIXED CODE ###

N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2)) # N mod 2
    N = -(N - N % 2) // 2 # (N − (N mod 2)) // 2
print("".join(list(reversed(a))))
### BUGGY CODE ###

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


t_min = min(S.count("#"), S.count("."))

for i in range(1,N):
    t = 0
    t += S[:i].count("#")
    t += S[i:].count(".")
    t_min = min(t_min, t)
print(t_min)

### FIXED CODE ###

N = int(input())
S = input()
t_min = min(S.count("#"), S.count("."))
S_first = 0
S_second = S.count(".")
for i in range(0,N):
    if S[i] == "#":
        S_first += 1
    else:
        S_second -= 1
    t = S_first + S_second
    t_min = min(t_min, t)
print(t_min)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

inf = 10**5
dp = [inf for i in range(n)]
dp[0] = 0

for i in range(1, n):
    tmp = []
    for j in range(i-k, i):
        if j >= 0:
            tmp.append(dp[j] + abs(h[j] - h[i]))
    dp[i] = min(tmp)

print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

inf = 10**5
dp = [inf for i in range(n)]
dp[0] = 0

for i in range(1, n):
    tmp = []
    for j in range(i-k, i):
        if j >= 0:
            tmp.append(dp[j] + abs(h[j] - h[i]))
    dp[i] = min(tmp)

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

n = int(input())
s = input()
def count(s):
  ans = 0
  for i in range(n-3):
    for j in range(i+1,n-1):
      for k in range(j+1,n):
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k] and k-j != j-i:
          ans += 1
  print(ans)
count(s)


### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b
for i in range(n):
  for j in range(i+1,n):
    k = 2*j-i
    if k < n:
      if  s[i] != s[j] and s[j]!= s[k] and s[i] != s[k]:
        ans -= 1
print(ans)
### BUGGY CODE ###

n = int(input())
d = set()
for i in range(n):
    c = input()
    if c[0] == 'i':
        d = d|{c[7:]}
    else:
        if c[5:] in d:
            print('yes')
        else:
            print('no')

### FIXED CODE ###

import sys
input()
r = sys.stdin.readlines()
d = {}

for i in r:
    if i[0] == 'i':
        d[i[7:]] = 0
    else:
        if i[5:] in d:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

def cnt_AC(n):
    return S[0:n].count("AC")

for i in range(Q):
    l, r = map(int, input().split())
    print(cnt_AC(r) - cnt_AC(l))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

t = [0] * (N + 1)

for i in range(N):
    t[i + 1] = t[i] + (1 if S[i:i + 2] == "AC" else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

import numpy as np
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
visited = np.zeros((h, w))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append((i, j, 0))
        visited[:, :] = 0
        while q:
            x, y, z = q.popleft()
            if z > ans: ans = z
            visited[x, y] = 1
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx, ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

N=int(input())
s=[sorted(list(input())) for i in range(N)]
from itertools import permutations, combinations,combinations_with_replacement,product
L = combinations(range(N), 2)   #nCr
cnt = 0
for i in L:
  if s[i[0]]==s[i[1]]:
    cnt +=1
print(cnt)


### FIXED CODE ###

N=int(input())
d={}
for i in range(N):
  a = "".join(sorted(list(input())))
  if a not in d:
    d[a] = 1
  else:
    d[a]=d[a]+1
cnt = 0
for B in d.values():
  cnt += int(B * (B-1) /2)
print(cnt)
### BUGGY CODE ###

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

ans = ''
temp = (A[1] - A[0])*2
for i in range(N)[2:]:
    temp = A[i]*2 - temp
a = int(temp/2)
ans = ans + str(a) + ' '

temp = a
for i in range(N-1):
    temp = A[i]*2 - temp
    ans = ans + str(temp) + ' '

print(ans.rstrip())

### FIXED CODE ###

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

ans = [] * (N)
temp = (A[1] - A[0])*2
for i in range(N)[2:]:
    temp = A[i]*2 - temp
a = int(temp/2)
ans.append(str(a))

temp = a
for i in range(N-1):
    temp = A[i]*2 - temp
    ans.append(str(temp))

print(' '.join(ans))
### BUGGY CODE ###

def main():
    import bisect

    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    def bise(x):
        count = 0

        for i in l:
            count += n-bisect.bisect_left(l,x-i)

        return count

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) > k:
            left = mid
        else:
            right = mid
    ans = []
    for i in l:
        for j in l:
            if i+j >= left:
                ans.append(i+j)
    ans.sort(reverse=True)
    
    print(sum(ans[0:k]))
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import bisect
    import numpy as np
    n,k = map(int,input().split())
    l = list(map(int,input().split()))
    l.sort()
    l1 = np.array(l)
    def bise(x):
        y = np.searchsorted(l1,x-l1)
        return n*n-y.sum()

    left = -1
    right = l[-1]*2+1

    while right > left+1:
        mid = (right+left)//2
        
        if bise(mid) >= k:
            left = mid
        else:
            right = mid
    ans = 0
    count = 0
    acc = [0]
    for i in l:
        acc.append(acc[-1]+i)
    for i in l:
        index = bisect.bisect_left(l,right-i)
        ans += i*(n-index) + acc[n]-acc[index]
        count += n-index

    print(ans-(count-k)*left)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

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

ans = [0 for _ in range(N)]

for i in range(N):
    sign = 1

    for a in A:
        ans[i] += sign * a
        sign *= -1

    t = A.pop(0)
    A.append(t)

print(*ans)

"""
ダム1: 2( a1 - a2 + a3 )
ダム2: 2( a2 - a3 + a1 )
ダム3: 2( a3 - a1 + a2 )
"""


### FIXED CODE ###

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

ans = [0 for _ in range(N)]

sign = 1
for a in A:
    ans[0] += sign * a
    sign *= -1


for i in range(1, N):
    ans[i] = 2 * A[0] - ans[i - 1]

    t = A.pop(0)
    A.append(t)

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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
#b=[0]*q
#c=[0]*q
for i in range(q):
    ans=0
    b, c=map(int,input().split())
    for j in range(n):
        if a[j] == b:
            a[j]=c
        ans+=a[j]
    print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
q=int(input())
#b=[0]*q
#c=[0]*q
ans=0
l=[0]*1000001
for i in range(n):
    ans+=a[i]
    l[a[i]]+=1

for i in range(q):
    b, c=map(int,input().split())
    x=c-b
    ans+=x*l[b]
    l[c]+=l[b]
    l[b]=0
    print(ans)