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

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


def main():
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()

    for i in range(1, N + 1):
        if seen[i] == 0:
            dfs(adj, i)

    print('Yes')


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


def main():
    t1 = time.time()
    N, M = map(int, input().split())
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        L, R, D = map(int, input().split())
        adj[L].append((R, D))
        adj[R].append((L, -D))
    seen = [0] * (N + 1)

    def dfs(adj, seen, start):
        inf = 10 ** 10
        que = deque()
        que.append(start)
        x = [inf] * (N + 1)
        x[start] = 0
        while que:
            v = que.pop()
            seen[v] = 1
            for u, d in adj[v]:
                if seen[u] == 0:
                    que.append(u)
                    if x[u] == inf:
                        x[u] = x[v] + d
                    else:
                        if x[u] != x[v] + d:
                            print('No')
                            sys.exit()
            t2 = time.time()
            if t2 - t1 > 1.8:
                print('Yes')
                sys.exit()
        return seen

    for i in range(1, N + 1):
        if seen[i] == 0:
            seen = dfs(adj, seen, i)

    print('Yes')


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

from math import log2,floor
N = int(input())
A = list(map(int,input().split()))
L = max([len(bin(x)) for x in A])
mod = 10**9+7
ans = 0
for i in range(L):
    bits = 0
    for x in A:
        if (x>>i)&1:
            bits += 1
    s = (bits*(N-bits))%mod
    t = (2**i)%mod
    ans = (ans+s*t)%mod
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
mod = 10**9 + 7
 
def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))
 
def main():
    n = ni()
    a = na()
    ans = 0
    for i in range(61):
        cnt = 0
        for ai in a:
            if (ai >> i) & 1:
                cnt += 1
        ans += ((cnt * (n - cnt)) * 2**i) % mod
    ans %= mod
    print(ans)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for _ in range(n):
    _list.append(int(input()))

maxi = 0
for i in range(n):
    if i==0:
        tmp_list = _list[1:]
    elif 0<i<n-1:
        tmp_list = _list[:i] + _list[i+1:]
    else:
        tmp_list = _list[:n-1]

    tmp_max = max(tmp_list)
    print(tmp_max)

### FIXED CODE ###

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

for _ in range(n):
    a.append(int(input()))

b = sorted(a, reverse=True)

for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

k, s = list(map(int, input().split()))

ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1

print(ans)

### FIXED CODE ###

k, s = list(map(int, input().split()))

ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            ans += 1

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

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,Ma,Mb = map(int,input().split())
    abc = [list(map(int,input().split())) for i in range(N)]

    INF = N * 100 + 1

    dp = [[[INF for cb in range(411)] for ca in range(411)] for i in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for ca in range(N*10):
            for cb in range(N*10):
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb],dp[i][ca][cb])
                d = abc[i]
                dp[i+1][ca+d[0]][cb+d[1]] = min(dp[i+1][ca+d[0]][cb+d[1]],dp[i][ca][cb]+d[2])

    res = INF

    for ca in range(1,401):
        for cb in range(1,401):
            if ca * Mb == cb * Ma:
                res = min(res,dp[N][ca][cb])

    if res == INF:
        res = -1

    print(res)



main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,Ma,Mb = map(int,input().split())
    abc = [list(map(int,input().split())) for i in range(N)]

    INF = N * 100 + 1

    dp = [[[INF for cb in range(411)] for ca in range(411)] for i in range(N+1)]
    dp[0][0][0] = 0

    for i in range(N):
        for ca in range(N*10):
            for cb in range(N*10):
                if dp[i][ca][cb] == INF:
                    continue
                dp[i+1][ca][cb] = min(dp[i+1][ca][cb],dp[i][ca][cb])
                d = abc[i]
                dp[i+1][ca+d[0]][cb+d[1]] = min(dp[i+1][ca+d[0]][cb+d[1]],dp[i][ca][cb]+d[2])

    res = INF

    for ca in range(1,401):
        for cb in range(1,401):
            if ca * Mb == cb * Ma:
                res = min(res,dp[N][ca][cb])

    if res == INF:
        res = -1

    print(res)



main()
### BUGGY CODE ###

import numpy as np
import bisect
N, M = map(int, input().split())
As = sorted(list(map(int, input().split())), reverse=True)
cards = np.array(As, dtype=np.int64) * -1

for i in range(M):
    B, C = map(int, input().split())

    p = bisect.bisect_right(cards, -C)
    if p >= N:
        continue

    replace = min(N - p, B)
    cards[p+replace:] = cards[p:N-replace]
    new_cards = np.array([-C]*replace, dtype=np.int64)
    cards[p:p+replace] = new_cards

total = 0
for card in cards:
    total += -card
print(total)

### FIXED CODE ###

import heapq
from collections import defaultdict

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

As = map(int, input().split())
counts = defaultdict(int)
for A in As:
    counts[A] += 1
h = sorted(counts.keys())

for i in range(M):
    B, C = map(int, input().split())

    if C not in counts:
        heapq.heappush(h, C)
    counts[C] += B
    if len(h) > N:
        v = heapq.heappop(h)
        del counts[v]

total_count = 0
total = 0
for k in sorted(h, reverse=True):
    c = counts[k]
    c = min(c, N - total_count)
    total += k * c
    total_count += c
    if total_count > N:
        break
print(total)
### BUGGY CODE ###

a, b, k = [ int(_) for _ in input().split() ]

if k >= a+b:
  print(0, 0)
  exit()

while k > 0:
  k -= 1
  if a >= 1:
    a -= 1
    pass
  elif b >= 1:
    b -= 1
    
print(a, b)

### FIXED CODE ###

a, b, k = [ int(_) for _ in input().split() ]

if k <= a:
  print(a-k, b)
elif a < k <= a+b:
  print(0, b-(k-a) )
elif a+b < k:
  print(0,0)
### BUGGY CODE ###

n  = int(input())

ans = 1
for i in range(1, n+1):
  ans = ans * i

s = 10**9 + 7

print(ans % s)

### FIXED CODE ###

import math
n  = int(input())
 
ans = math.factorial(n)
 
s = 10**9 + 7
 
print(ans % s)
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
#def MXI(): return [LI() for i in range(n)]　
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
height=LI()
dp=[inf for i in range(n)]
dp[0]=0
for i in range(1,n):
    for j in range(1,min(i,k)+1):
        dp[i]=min(dp[i],dp[i-j]+abs(height[i]-height[i-j]))
print(dp[-1])
    








            
    
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()

n,k=MI()
hs=LI()
dp=[inf for i in range(n)]
dp[0]=hs[0]

for i in range(min(n,k)):
    dp[i]=abs(hs[i]-hs[0])
for i in range(n):
    mn=dp[i]
    for j in range(1,k+1):
        if i-j>=0:
            u=dp[i-j]+abs(hs[i]-hs[i-j])
            if u<mn:
                mn=u
    dp[i]=mn
print(dp[-1])
### BUGGY CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)

### FIXED CODE ###

S=input()
T=input()
dp=[[0 for j in range(len(T)+1)] for i in range(len(S)+1)]
for i in range(len(S)):
    for j in range(len(T)):
        if S[i]==T[j]:
            dp[i+1][j+1]=dp[i][j]+1
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i+1][j])
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j+1])
i=len(S)
j=len(T)
ans=""
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=S[i-1]+ans
        i-=1
        j-=1
print(ans)
### BUGGY CODE ###

def G(N,R):
	X=1
	for I in range(min(R,N-R)):X=X*(N-I)*F(I+1)%M
	return X
F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=G(H+W-2,H-1)
for I in range(B):C=(C*(H-A+I-1)*F(I)*(W-I)*F(A+W-I-1)if I else G(H-A+I-1,H-A-1)*G(A+W-I-2,A-1))%M;Z=(Z-C)%M
print(Z%M)

### FIXED CODE ###

F=lambda X:pow(X,M-2,M);M=10**9+7;H,W,A,B=map(int,input().split());Z=C=1
for I in range(min(W-1-B,H-1)):Z=C=C*(W+H-B-2-I)*F(I+1)%M
for I in range(1,H-A):C=C*(B-1+I)*F(I)*(H-I)*F(W+H-B-1-I)%M;Z=(Z+C)%M
print(Z)
### BUGGY CODE ###

import bisect

n, q = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]

rws.sort(key = lambda x: x[2])
ans = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if ans[st] == -1:
			ans[st] = rw[2]
		st += 1

for a in ans:
	print(a)

### FIXED CODE ###

import bisect

n, q = list(map(int, input().split()))
rws = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]

rws.sort(key = lambda x: x[2])

ans = [-1 for _ in range(q)]
nxt = [-1 for _ in range(q)]
for rw in rws:
	st = bisect.bisect_left(ds, rw[0] - rw[2])
	en = bisect.bisect_left(ds, rw[1] - rw[2])
	while st < en:
		if nxt[st] == -1:
			ans[st] = rw[2]
			nxt[st] = en
			st += 1
		else:
			st = nxt[st]

for a in ans:
	print(a)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
Exp = [list(map(int,input().split())) for i in range(M)]
Query = [list(map(int,input().split())) for i in range(Q)]
for q in Query:
    ans = 0
    for e in Exp:
        if q[0] <= e[0] and e[1] <= q[1]:
            ans += 1
    print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
memo = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l][r] += 1
for i in range(N):
    for j in range(N):
        memo[i+1][j+1] += memo[i][j+1] + memo[i+1][j] - memo[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])
### BUGGY CODE ###

N = int(input())
a = [list(map(int, input().split())) for i in range(N)]


def popcount(x):
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
    x = x + (x >> 8)  # 16bitごと
    x = x + (x >> 16)  # 32bitごと
    x = x + (x >> 32)  # 64bitごと = 全部の合計
    return x & 0x0000007f


dp = [[0]*(1 << N) for i in range(N+1)]
dp[0][0] = 1
mod = 10**9+7
for j in range(1, 1 << N):
    i = popcount(j)
    for k in range(N):
        if (j >> k) % 2 == 1:
            if a[i-1][k] == 1:
                dp[i][j] += dp[i-1][j ^ (1 << k)]
                dp[i][j] %= mod

print(dp[-1][(1 << N) - 1])


### FIXED CODE ###

def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]

    def popcount(x):
        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f  # 8bitごと
        x = x + (x >> 8)  # 16bitごと
        x = x + (x >> 16)  # 32bitごと
        x = x + (x >> 32)  # 64bitごと = 全部の合計
        return x & 0x0000007f

    dp = [[0]*(1 << N) for i in range(N+1)]
    dp[0][0] = 1
    mod = 10**9+7
    for j in range(1, 1 << N):
        i = popcount(j)
        DP = dp[i]
        prev = dp[i-1]
        for k in range(N):
            if (j >> k) % 2 == 1:
                if a[i-1][k] == 1:
                    DP[j] += prev[j ^ (1 << k)]
                    DP[j] %= mod

    print(dp[-1][(1 << N) - 1])


main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=0
while len(a)>0:
    if sorted(a) == a:
        print(s)
        exit()
    else:
        x=max(a)
        k=a.index(x)
        s=s+x*(len(a)-1-k)-sum(a[k+1:])
        #for i in range(k+1,len(a)):s+=x-a[i]
        a=a[:k]
print(s)





### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
mx=a[0]
for x in a:
    if mx>x:ans+=mx-x
    else:mx=x
print(ans)
### BUGGY CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

for i in range(N):
    for sum_w in range(W+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w])

print(dp[N][W])

### FIXED CODE ###

def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

N,W = MAP()
weight=[]
value=[]
for i in range(N):
    w,v = MAP()
    weight.append(w)
    value.append(v)

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

for i in range(N):
    for sum_w in range(W+1):
        if sum_w-weight[i]>=0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w-weight[i]]+value[i])

        dp[i+1][sum_w] = max(dp[i+1][sum_w],dp[i][sum_w])

print(dp[N][W])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import numpy as np
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    index = np.argsort(l)

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                a = l[index[i]]
                b = l[index[j]]
                c = l[index[k]]
                if c < a + b:
                    result += 1
                else:
                    break

    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()

    result = 0
    for i in range(n-2):
        for j in range(i + 1, n - 1):
            result += bisect.bisect_left(l, l[i] + l[j]) - (j + 1)

    print(result)


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

from math import sqrt, floor
from collections import defaultdict


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

X = defaultdict(int)
cnt = 2
while True:
    if P == 1 or cnt > P:
        break
    if P % cnt == 0:
        X[cnt] += 1
        P = P // cnt
    else:
        cnt += 1

ans = 1
for k, v in X.items():
    ans *= k ** (v // N)
print(ans)


### FIXED CODE ###

from math import sqrt, floor
from collections import defaultdict


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

X = defaultdict(int)
cnt = 2
for a in range(2, floor(sqrt(P)) + 1):
    while P % a == 0:
        X[a] += 1
        P = P // a
if P > 1:
    X[P] += 1

ans = 1
for k, v in X.items():
    ans *= k ** (v // N)
print(ans)
### BUGGY CODE ###

from functools import reduce
from operator import mul


def main():
    N, K = map(int, input().split())
    print(sum(reduce(mul, (0.5
                           for j in range(K)
                           if i << j < K), 1 / N)
              for i in range(1, N + 1)))
    return


main()


### FIXED CODE ###

from functools import reduce
from operator import mul


def main():
    N, K = map(int, input().split())
    ans = []
    lst = []
    for i in range(1, N + 1):
        lst.clear()
        for j in range(K):
            if K <= i << j:
                break
            lst.append(0.5)
        ans.append(reduce(mul, lst, 1 / N))
    print(sum(ans))
    return


main()
### BUGGY CODE ###

import bisect
 
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
def f(t,A,B):
	power = (1<<t)
	AA = [x%(2*power) for x in A]
	BB = [x%(2*power) for x in B]
	AA.sort()
	BB.sort()
	cnt = 0
	for i in range(N):
		a = AA[i]
		R = bisect.bisect_right(BB, power-1-a)
		cnt += R
		L = bisect.bisect_left(BB,2*power-a)
		R = bisect.bisect_right(BB, 3*power-1-a)
		cnt += R-L
	x0 = cnt
	x1 = N*N - cnt
	return x1%2
  
ans = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		ans += 1<<t
 
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
 
def sum_count(A,B,x):
    # A,B is sorted. 
    # return count(a+b < x)
    p = len(B)-1
    result = 0
    for a in A:
        while p != -1 and a + B[p] >= x:
            p -= 1
        result += p+1
    return result
 
		
def f(t,A,B):
    power = (1<<t)
    AA = [x&(2*power-1) for x in A]
    BB = [x&(2*power-1) for x in B]
    AA.sort()
    BB.sort()
    
    x1,x2,x3 = (sum_count(AA,BB,v) for v in [power, 2*power, 3*power])
    zero_cnt = x1 + (x3-x2)
    return (N-zero_cnt)%2
  
ans = 0
for t in range(30):
	x = f(t,A,B)
	if x == 1:
		ans += 1<<t
 
print(ans)
### BUGGY CODE ###

import bisect


class SegTree:

    def __init__(self, n):
        # supposed that n = 2**m
        INF = 10 ** 12
        self.n = n
        self.val = [INF for _ in range(2 * n + 1)]

    def _update(self, a, b, v, k, l, r):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = min(v, self.val[k])
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)

    def update(self, a, b, v):
        # 区間[a, b)上の値がvより大きければvに更新
        self._update(a, b, v, 0, 0, self.n)

    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = min(ret, self.val[k])
        return ret


def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for _ in range(N)]
    # 工事は出発地から近い順に並べておく
    work_list.sort(key=lambda work: work[2])
    D = [int(input()) for _ in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w in range(N):
        s, t, x = work_list[w]
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree.update(left, right, w)
    for q in range(Q):
        w = tree.query(q)
        if w >= N:
            print(-1)
        else:
            print(work_list[w][2])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

def calc_comb(lst_A):

    elem_A = list(set(lst_A))
    sum_comb = 0

    for A in elem_A:
        numA  = lst_A.count(A)
        combA = (numA * (numA-1)) // 2
        sum_comb += combA

    return sum_comb

def main(N, lst_A):

    sum_comb_all = calc_comb(lst_A)

    for A in lst_A:
        numA = lst_A.count(A)
        prev_combA = (numA * (numA-1)) // 2
        new_combA  = ((numA-1) * (numA-2)) // 2

        sum_comb = sum_comb_all - prev_combA + new_combA
        
        print(sum_comb)

if __name__ == "__main__":

    main(N, lst_A)
    

### FIXED CODE ###

from collections import Counter

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

def main(N, lst_A):

    dct_cntA = Counter(lst_A)
    sum_comb = 0

    for cntA in dct_cntA.values():
        comb = (cntA * (cntA - 1)) // 2
        sum_comb += comb

    for A in lst_A:
        print(sum_comb - (dct_cntA[A] - 1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)