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

#python3
def main():
    n, m = map(int, input().split())
    a = [int(i) for i in input().split()]
    for _ in range(m):
        b, c = map(int, input().split())
        a.extend([c for _ in range(b)])     
    a.sort(reverse=True)
    ans = sum(a[:n])
    print(ans)
main()


### FIXED CODE ###

#python3
from heapq import heappop, heappush

def main():
    n, m = map(int, input().split())
    hq = [] 
    for i in input().split():
        heappush(hq, (-int(i), 1))
    for _ in range(m):
        b, c = map(int, input().split())
        heappush(hq, (-c, b))
    ans = 0
    for i in range(n):
        v, u = heappop(hq)
        u = u - 1
        if u >= 1:
            heappush(hq, (v, u))
        v = - v 
        ans = ans + v
    print(ans)
main()
### BUGGY CODE ###

N, M=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
for i in range(M):
  A[-1]=A[-1]//2
  A.sort()
print(sum(A))

### FIXED CODE ###

import heapq
N, M=map(int, input().split())
A=list(map(int, input().split()))
A=list(map(lambda x: -x, A))
heapq.heapify(A)
for i in range(M):
  heapq.heappush(A, (heapq.heappop(A)+1)//2)
print(-sum(A))
### BUGGY CODE ###

def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[target] = 0 # default + max
    max_ = 0

    for vi in range(len(V)):
        we = W[vi]
        va = V[vi]
        for i in list(P.keys()):
            if i >= we:
                prev = P[i-we] if (i-we) in P else -1
                piva = P[i] + va
                if prev < piva:
                    P[i - we] = piva
                    if piva > max_:
                        max_ = piva

    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)


### FIXED CODE ###

def knapsack_rec(target, W, V): # target=knapsack weight
    P = {}
    P[0] = target
    max_ = 0

    for vi in range(len(V)):
        we, va = W[vi], V[vi]
        for i in range(max_, -1, -1):
            if i in P:
                piva = P.get(i + va, -1)
                if piva < P[i] - we:
                    P[i + va] = P[i] - we
                    if max_ < i + va:
                        max_ = i + va
    return max_

assert knapsack_rec(15, [6, 5, 6, 6, 3, 7], [5, 6, 4, 6, 5, 2]) == 17

if __name__ == "__main__":
    import sys
    n, w, *r = map(int, sys.stdin.read().split())
    W, V = r[::2], r[1::2]
    ans = knapsack_rec(w, W, V)
    print(ans)
### BUGGY CODE ###

INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

N,M = map(int,input().split())
MOD = M
G = [[] for _ in range(N)]
for _ in range(N - 1):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)
    G[y].append(x)

deg = [0] * N
dp = [None] * N
parents = [0] * N
ans = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    res = 1
    dp[v] = [0] * deg[v]
    for i,e in enumerate(G[v]):
        if e == p:
            parents[v] = i
            continue
        dp[v][i] = dfs(e,v)
        res *= dp[v][i] + 1
        res %= MOD
    return res

def bfs(v,res_p = 0,p = -1):
    if p != -1:
        dp[v][parents[v]] = res_p
    dpl = [1]*(deg[v] + 1)
    dpr = [1]*(deg[v] + 1)
    for i in range(deg[v]):
        dpl[i + 1] = dpl[i]*(dp[v][i] + 1)%MOD
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*(dp[v][i] + 1)%MOD
    ans[v] = dpr[0]
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]%MOD,v)

dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 10

MAXN = 100005
G = [[] for _ in range(MAXN)]
dp = [[] for _ in range(MAXN)]
deg = [0] * MAXN
parents = [-1] * MAXN
result = [0] * MAXN

def dfs1(v,mod,p = -1):
    ans = 1
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            parents[v] = i
            continue
        dp[v][i] = dfs1(e,mod,v)
        ans *= dp[v][i] + 1
        ans %= mod
    return ans%mod

def dfs2(v,mod,res_p = 1,p = -1):
    if p != -1:
        dp[v][parents[v]] = res_p
    cuml = [1] * (deg[v] + 1)
    cumr = [1] * (deg[v] + 1)
    for i in range(deg[v]):
        cuml[i + 1] = cuml[i] * (1 + dp[v][i]) % mod
    for i in range(deg[v] - 1,-1,-1):
        cumr[i] = cumr[i + 1] * (1 + dp[v][i]) % mod
    result[v] = cumr[0]
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            continue
        dfs2(e,mod,cuml[i] * cumr[i + 1] % mod,v)

def main():
    n,m = map(int,input().split())
    for _ in range(n - 1):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        G[x].append(y)
        G[y].append(x)
    
    for i in range(n):
        deg[i] = len(G[i])
        dp[i] = [1] * deg[i]
    
    dfs1(0,m)
    dfs2(0,m)
    for i in range(n):
        print(result[i])      

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,0,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  x=0
  for j in range(i,n):
    x+=a[j]
    b.append(x)
ans=0
l=len(b)
for i in range(40,-1,-1):
  x=0
  s=2**i
  for j in range(l):
    if b[j]&(ans+s)==ans+s:x+=1
  if x>=k:ans+=s
print(ans)
### BUGGY CODE ###

import numpy as np

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = np.array(input().split(' '), dtype='i')
    for _ in range(num_coupon):
        prices[prices.argmax()] //= 2
    print(prices.sum())

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)


### FIXED CODE ###

import heapq

def receive_shopping_plan():
    num_commodity, num_coupon = input().split(' ')
    num_commodity, num_coupon = int(num_commodity), int(num_coupon)
    return num_commodity, num_coupon

def calc_minimized_sum(num_commodity, num_coupon):
    prices = list(map(lambda x: int(x) * -1 , input().split(' ')))
    heapq.heapify(prices)
    for _ in range(num_coupon):
        max_price = heapq.heappop(prices) // (2*-1)
        heapq.heappush(prices, max_price*-1)

    print(sum(prices)*-1)

if __name__ == '__main__':
    num_commodity, num_coupon = receive_shopping_plan()
    calc_minimized_sum(num_commodity, num_coupon)
### BUGGY CODE ###

MOD = 1000000007
n = int(raw_input())
a = [int(_) for _ in raw_input().split()]
d = {}
for i, ai in enumerate(a):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai


def ncr(n, r):
    if r * 2 > n:
        return ncr(n, n - r)
    ans = 1
    for i in xrange(n - r + 1, n + 1):
        ans *= i
    for i in xrange(1, r + 1):
        ans //= i
    return ans


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        s = max(0, k - 1 - r)
        while s <= l and s <= k - 1:
            e = k - 1 - s
            a -= (ncr(l, s) % MOD) * (ncr(r, e) % MOD) % MOD
            s += 1
    print a % MOD


### FIXED CODE ###

MOD = 1000000007
n = int(raw_input())
d = {}
for i, ai in enumerate(int(_) for _ in raw_input().split()):
    if ai in d:
        stt = d[ai]
        end = i
        break
    d[ai] = i
del d, i, ai

fac = {0: 1}
facinv = {}
for i in xrange(1, n + 2):
    fac[i] = fac[i - 1] * i % MOD
facinv[n + 1] = pow(fac[n + 1], MOD - 2, MOD)
for j in xrange(n, -1, -1):
    facinv[j] = facinv[j + 1] * (j + 1) % MOD


def ncr(n, r):
    return (fac[n] * facinv[n - r] * facinv[r]) % MOD


l = stt
r = n - end

for k in xrange(1, n + 2):
    a = ncr(n + 1, k) % MOD
    if l + r >= k - 1:
        a -= ncr(l + r, k - 1) % MOD
    print a % MOD
### BUGGY CODE ###

S=raw_input()
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7


for i in range(1,l+1):
	dp2=[ 0 for _ in range(13) ]
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*pow(10,l-i,13)+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*pow(10,l-i,13)+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod
	dp=dp2

print dp[5]


### FIXED CODE ###

S=raw_input()
S=S[::-1]
l=len(S)

dp=[ 0 for j in range(13) ]
dp[0]=1

mod=10**9+7

dp2=[ 0 for _ in range(13) ]

keta=1

for i in range(1,l+1):
	dp2=[0]*13
	for j in range(13):
		if dp[j]!=0:
			if S[i-1]=="?":
				for k in range(10):
					next=(k*keta+j)%13 
					dp2[next]+=dp[j]
					dp2[next]%=mod
			else:
				k=int(S[i-1])
				next=(k*keta+j)%13
				dp2[next]+=dp[j]
				dp2[next]%=mod

	dp=dp2
	keta=(keta*10)%13

print dp[5]
### BUGGY CODE ###

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

N, K = list(map(int, input().split()))
ab = []
for i in range(N-1):
    ab.append(list(map(int, input().split())))

ki = []

for i in range(N):
    ki.append(dict())
    ki[-1]["eda"] = []

for i in range(N-1):
    ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
    ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])

def P(m ,n):
    num = 1
    for i in range(n):
        num *= m-i
    return num



total_num = K
judge = [False]*N
if len(ki[0]["eda"]) != 0:
    total_num *= P(K-1, len(ki[0]["eda"]))
    judge[0] = True
    node = deque([])
    for edge in ki[0]["eda"]:
        node.append(edge[1])
    while len(node) != 0:
        i = node.popleft()
        judge[i] = True

        for edge in ki[i]["eda"]:
            if not judge[edge[1]]:
                node.append(edge[1])
        total_num *= P(K-2, len(ki[i]["eda"])-1)
        total_num = total_num % 1000000007
        if total_num == 0:
            break

print(total_num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

n = max(A)

is_prime = [True]*(n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5)+1):
    if not is_prime[i]:
        continue
    for j in range(i*2, n+1, i):
        is_prime[j] = False
primes = [i for i in range(n+1) if is_prime[i]]

for p in primes:
    flag = 0
    for i in range(N):
        if A[i] % p == 0:
            if flag:
                break
            flag = 1
    else:
        continue

    # not pairwise coprime
    gcd_set = reduce(gcd, A)
    if gcd_set == 1:
        print("setwise coprime")
    else:
        print('not coprime')
    exit()
print('pairwise coprime')

    


### FIXED CODE ###

from math import gcd
from functools import reduce
N = int(input())
*A, = map(int, input().split())

MAX_N = max(A)+5
primes = list(range(MAX_N+1))
for i in range(2, int(MAX_N**0.5)+1):
    if primes[i] < i:
        continue
    for j in range(2*i, MAX_N+1, i):
        primes[j] = i


def check():
    S = set()
    for a in A:
        T = set()
        while True:
            p = primes[a]
            if p != 1 and p in S:
                return False
            T.add(p)
            if p == a:
                break
            a //= p
        S |= T
    return True


if check() or all(a == 1 for a in A):
    print('pairwise coprime')
elif reduce(gcd, A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

# https://atcoder.jp/contests/abc097/tasks/arc097_a
# まずは愚直に実装してみる

S = input()
K = int(input())
candi = []
for s in range(len(S)):
    for e in range(s + 1, len(S) + 1):
        candi.append(S[s:e])
candi = list(set(candi))
candi.sort()
print(candi[K - 1])


### FIXED CODE ###

# https://atcoder.jp/contests/abc097/tasks/arc097_a


# 辞書順に置いては文字の先頭が重要。
# 一文字目が速いやつから注目していく。
# 一文字目が同じだったらさらにその次の文字を注目する。

# atcoderandatcodeer
# a      a  a       # 1種
# at     an at      # 1種 #tは以下のすべてよりも辞書順があと
#        and        # 1種
#        anda       # 1種
#        andat      #

S = input()
K = int(input())

# 一番速い文字を検索してからそこからK文字見るのが一番早そう。
# ただし、K文字ない場合は辻褄合わせが必要
# てか計算量的に、こんなことしなくてもK文字目まで全列挙すればよくね？

# mi = min(S)
candi = []
for s in range(len(S)):
    for add in range(1, K + 1):
        candi.append(S[s:s + add])

candi = list(set(candi))
candi.sort()
print(candi[K - 1])
### BUGGY CODE ###

from itertools import accumulate,zip_longest
from functools import reduce
import bisect
import sys
input = sys.stdin.readline

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

B = [2*a+1 for a in A] # right
A = [2*a for a in A] # left
X = [2*x for x in X]

S = list(accumulate(A))
T0 = accumulate(A[::2])
T1 = accumulate(A[1::2])
T = list(reduce(lambda x,y : x+y, zip_longest(T0,T1)))
if T[-1] is None:
    T.pop()

maxhigh = 10**16
for x in X:
    if x > (A[-1]+A[-2])//2:
        print(T[-1]//2)
        continue
    NG = maxhigh
    OK = 0
    R = OK
    ans = 0
    while True:
        l = x - R
        r = x + R
        li = bisect.bisect_left(A,l)
        ri = bisect.bisect_right(B,r)
        #print(l,r,li,ri)
        M = ri-li
        if ri == N-M:
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            #print("HER",li,ri)
            li -= 1
            if li > 0:
                ans += T[li-1]
            break
        if ri < N-M:
            OK = R
            R = (R + NG)//2
        if N-M < ri:
            NG = R
            R = (R + OK)//2
        #print(l,x,r,li,ri,OK,"R",R,NG)
    #print(l,x,r,li,ri,OK,R,NG)
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans//2)



### FIXED CODE ###

from itertools import accumulate,zip_longest
from functools import reduce
import bisect
import sys
input = sys.stdin.readline

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

B = [2*a+1 for a in A] # right
A = [2*a for a in A] # left
X = [2*x for x in X]

S = list(accumulate(A))
T0 = accumulate(A[::2])
T1 = accumulate(A[1::2])
T = []
for s,t in zip_longest(T0,T1):
    T.append(s)
    T.append(t)
if T[-1] is None:
    T.pop()

maxhigh = 10**16
for x in X:
    if x > (A[-1]+A[-2])//2:
        print(T[-1]//2)
        continue
    NG = maxhigh
    OK = 0
    R = OK
    ans = 0
    while True:
        l = x - R
        r = x + R
        li = bisect.bisect_left(A,l)
        ri = bisect.bisect_right(B,r)
        M = ri-li
        if ri == N-M:
            if li > 0:
                ans += T[li-1]
            break
        if ri == N-M-1:
            li -= 1
            if li > 0:
                ans += T[li-1]
            break
        if ri < N-M:
            OK = R
            R = (R + NG)//2
        if N-M < ri:
            NG = R
            R = (R + OK)//2
    if ri > 0:
        ans += S[N-1] - S[ri-1]
    else:
        ans += S[N-1]
    print(ans//2)
### BUGGY CODE ###

n = int(input())

a = [0 for i in range(10**9)]

for i in range(n):
    k = int(input())
    a[k-1] += 1
co = 0
for i in range(10**9):
    if a[i] % 2 == 1:
        co += 1
print(co)

### FIXED CODE ###

import collections

n = int(input())

co = collections.Counter([int(input()) for i in range(n)])

c =0

for i in co.values():
    if i % 2 != 0:
        c  +=1
print(c)
### BUGGY CODE ###

from array import array
from itertools import accumulate, islice, repeat
from operator import itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(sum(map(itemgetter(q), islice(city_list, p, q + 1))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for _ in range(express_count):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(city_list[q][q] - city_list[p - 1][q])


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

N = int(input())
A = list(map(int, input().split()))
S = sum(A)
A.extend(A)
B = []
for i in range(N):
	x = 0
	for j in range((N - 1) // 2):
		x += A[i + 2 * j + 1]
	B.append(S - 2 * x)
C = [str(a) for a in B]
print(' '.join(C))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sum(A)
B = []
x = 0
for j in range((N - 1) // 2):
	x += A[2 * j + 1]
B.append(S - 2 * x)
for i in range(N - 1):
	x = A[i] * 2 - B[i]
	B.append(x)
C = [str(a) for a in B]
print(' '.join(C))
### BUGGY CODE ###

def combination(a, b) :
    ans1 = 1
    ans2 = 1
    if a//2 < b :
        b = a-b
    for l in range(a, a-b, -1) :
        ans1 = (ans1*l)%(10**9+7)
    for m in range(1, b+1) :
        ans2 = (ans2*m)%(10**9+7)
    return ans1/ans2

ans = 0
n, a, b = map(int, input().split())
for i in range(1, n+1) :
    if i == a or i == b :
        continue
    plus = combination(n, i) % (10**9+7)
    ans = (ans+plus) % (10**9+7)
print(int(ans))

### FIXED CODE ###

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

def comb(n, r, mod) :
    ans1 = 1
    ans2 = 1
    for i in range(r) :
        ans1 = (ans1 * (n-i)) % mod
        ans2 = (ans2 * (i+1)) % mod
    return ans1 * pow(ans2, mod-2, mod)

ans = pow(2, n, mod) - comb(n, a, mod) - comb(n, b, mod) - 1
print(ans%mod)
### BUGGY CODE ###

from operator import itemgetter
import numpy as np
from numba import njit


def f(idx):
    ret = np.zeros((1 << n, n), np.int64)

    for i in range(1 << n):
        lines = [0]
        now = i
        for j in range(n):
            if now & 1:
                lines.append(xyp[j][idx])
            now >>= 1

        for j, (e, p) in enumerate(map(itemgetter(idx, 2), xyp)):
            dist = INF
            for el in lines:
                dist = min(dist, abs(e - el))

            ret[i, j] = dist * p

    return ret


@njit
def pow3topow2(pow3):
    v = 0
    h = 0
    cnt = 0
    pow2 = 1
    while pow3:
        pow3, r = divmod(pow3, 3)
        if r == 1:
            v += pow2
            cnt += 1
        elif r == 2:
            h += pow2
            cnt += 1

        pow2 *= 2

    return v, h, cnt


n = int(input())
xyp = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 18

ver = f(0)
hor = f(1)

ans = [INF] * (n + 1)
for i in range(3 ** n):
    vi, hi, cnt = pow3topow2(i)

    score = np.minimum(ver[vi], hor[hi]).sum()

    ans[cnt] = min(ans[cnt], score)

print(*ans, sep="\n")


### FIXED CODE ###

import numpy as np
from numba import njit, int64
import sys

read = sys.stdin.buffer.read


@njit((int64[:], ), cache=True)
def solve(inp):
    INF = 10 ** 18

    n = inp[0]
    x = inp[1::3]
    y = inp[2::3]
    p = inp[3::3]

    ver = np.empty((1 << n, n), np.int64)
    ver[0] = np.abs(x) * p

    for i in range(n):
        bt = 1 << i
        ver[bt:2 * bt] = np.minimum(ver[:bt], np.abs(x - x[i]) * p)

    hor = np.empty((1 << n, n), np.int64)
    hor[0] = np.abs(y) * p

    for i in range(n):
        bt = 1 << i
        hor[bt:2 * bt] = np.minimum(hor[:bt], np.abs(y - y[i]) * p)

    ans = [INF] * (n + 1)
    for i in range(pow(3, n)):
        vi = 0
        hi = 0
        cnt = 0
        pow2 = 1
        pow3 = i
        while pow3:
            pow3, r = divmod(pow3, 3)
            if r == 1:
                vi += pow2
                cnt += 1
            elif r == 2:
                hi += pow2
                cnt += 1

            pow2 *= 2

        score = np.minimum(ver[vi], hor[hi]).sum()
        ans[cnt] = min(ans[cnt], score)

    return ans


inp = np.array(read().split(), np.int64)
ans = solve(inp)
print(*ans, sep="\n")
### BUGGY CODE ###

from operator import mul
from functools import reduce

def combinations_count(n, r):
    #r = min(r, n - r)
    if r > n:
        return 0
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

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

d = dict()
for a in A:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1

if len(d) == n:
    for i in range(n):
        print(0)
    exit()

d1 = dict()
for a in d.keys():
    d1[a] = combinations_count(d[a], 2)

ans = []
d3 = dict()
for a in A:
    if a not in d3.keys():
        ans.append(sum(d1.values()) - (d[a] - 1))
    else:
        ans.append(d3[a])

for a in ans:
    print(a)

### FIXED CODE ###

from operator import mul
from functools import reduce

def combinations_count(n, r):
    #r = min(r, n - r)
    if r > n:
        return 0
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

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

d = dict()
for a in A:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1

if len(d) == n:
    for i in range(n):
        print(0)
    exit()

d1 = dict()
for a in d.keys():
    d1[a] = combinations_count(d[a], 2)

d2 = dict()
for a in d.keys():
    d2[a] = combinations_count(d[a] - 1, 2)

ans = []
d3 = dict()
s = sum(d1.values())
for a in A:
    if a not in d3.keys():
        ans.append(s - d1[a] + d2[a])
    else:
        ans.append(d3[a])

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

import math
k = int(input())
cnt = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            cnt += math.gcd(math.gcd(a, b), c)
print(cnt)

### FIXED CODE ###

import math
k = int(input())
cnt = 0
for a in range(1, k+1):
    for b in range(a+1, k+1):
        for c in range(b+1, k+1):
            cnt += math.gcd(math.gcd(a, b), c) * 6

for a in range(1, k+1):
    for b in range(a+1, k+1):
        cnt += math.gcd(a, b) * 6

for i in range(1, k+1):
    cnt += i
print(cnt)