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

import itertools

X, Y, Z, K  = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse = True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse = True)

for i in range(K):
    print(ans[i])

### FIXED CODE ###

X, Y, Z, K  = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

l = []
for a in A:
    for b in B:
        l.append(a+b)
l = sorted(l, reverse = True)[:K]

ans = []
for c in C:
    for k in l:
        ans.append(c + k)
        
ans = sorted(ans, reverse = True)
print(*ans[:K], sep="\n")
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()

arr = [[a[i], i + 1] for i in range(n)]
arr.sort()

ans = 0
for i in range(n - 1): #低い方
    if arr[i][0] + arr[i + 1][0] > n:
        continue
    for j in range(i + 1, n): #高い方
        if arr[i][0] + arr[j][0] == abs(arr[i][1] - arr[j][1]):
            ans += 1

print(ans)


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

#にぶたんサーチ
def search(arr, num):
    l = 0
    r = len(arr) - 1
    while r - l > 1:
        c = (r + l) // 2
        if arr[c] > num:
            r = c
        elif arr[c] < num:
            l = c
        else:
            r = c
            l = c
    if arr[l] == num:
        return l
    elif arr[r] == num:
        return r
    else:
        return -1

n = INT()
a = LIST()

l = [i + 1 + a[i] for i in range(n)]
r = [i + 1 - a[i] for i in range(n)]
b = Counter(r)
c = list(set(r))
c.sort()
ans = 0
for i in l:
    if search(c, i) < 0:
        continue
    ans += b[i]

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

n, m, k =map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
ta=0
tb=0
ans=0
for i in range(n+1):
    if i>0:
        ta += a[i-1]

    if ta>k:
        break
    for j in range(m):
        tb=sum(b[:j+1])
        ans=max(ans,i+j)
        if tb + ta >k:
            break
        ans=max(ans,i+j+1)
print(ans)


### FIXED CODE ###

n, m, k =map(int, input().split())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
ta=sum(a)
a.append(0)
tb=0
ans=0
j=0
for i in range(n+1):
    ta -= a[n-i]
    if ta>k:
        continue
    while tb + ta<=k:

        if j ==m:
            ans=max(ans,n-i+j)
            break
        ans=max(ans,n-i+j)
        tb += b[j]
        j +=1

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

import numpy as np
import sys
def input(): return sys.stdin.readline()

n=int(input())
a=np.array(list(map(int,input().split())))
 
ans=0
#print(a%(np.array([a for _ in range(n)])).transpose())
 
for A in a:
  b=A%a==0
  #print(b)
  if np.count_nonzero(b)==1:
    ans+=1
print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline()

n=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6+2)
ans=0
for a in A:
  if cnt[a]!=0:
    cnt[a]=2
    continue
  x=a
  while x<10**6+2:
    cnt[x]+=1
    x+=a
for a in A:
  #print(cnt[a])
  if cnt[a]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)
def multi_gcd(l):
  if len(l) == 1:
    return l[0]
  else:
    new_l = []
    if len(l)%2 == 0:
      for i in range(len(l)//2):
        new_l.append(gcd(l[2*i], l[2*i+1]))
      return multi_gcd(new_l)
    else:
      for i in range(len(l)//2):
        new_l.append(gcd(l[2*i], l[2*i+1]))
      new_l.append(l[-1])
      return multi_gcd(new_l)
     
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
  a_gcd = multi_gcd(a[:i]+a[i+1:])
  if ans < a_gcd:
    ans = a_gcd
print(ans)

### FIXED CODE ###

def gcd(a, b):
  if a%b == 0:
    return b
  else:
    return gcd(b, a%b)
def mgcd(l):
  if len(l) == 1:
    return l[0]
  else:
    new_l = []
    for i in range(-(-len(l)//2)):
      temp = gcd(l[i], l[-i-1])
      if temp == 1:
        return 1
      else:
        new_l.append(temp)
    return mgcd(new_l)

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans1 = mgcd(a[1:])
min_gcd = 1001001001
min_idx = 0
for i in range(1,n):
  temp = gcd(a[0], a[i])
  if temp < min_gcd:
    min_gcd = temp
    min_idx = i
a.pop(min_idx)
ans2 = mgcd(a)
print(max(ans1, ans2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


def DFS(point,left,right,cnt):
    global ans
    if point<=k:
        if cnt>ans:
            ans=cnt

    if left<n:DFS(point+A[left],left+1,right,cnt+1)
    if right<m:DFS(point+B[right],left,right+1,cnt+1)


n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
DFS(0,0,0,0)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))

for i in range(1,n+1):
    A[i]=A[i-1]+A[i]
for i in range(1,m+1):
    B[i]=B[i-1]+B[i]

ans,j=0,m
for i in range(n+1):
    if A[i]>k:break
    while B[j]>k-A[i]:
        j -=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
import networkx as nx
g = nx.DiGraph()
for i in range(n):
    g.add_node(i)
for _ in range(m):
    u,v = map(int, input().split())
    g.add_edge(u,v)
comp = list(nx.strongly_connected_components(g))
print(len(comp))
for item in reversed(comp):
    print(len(item), " ".join(map(str, item)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].append(v)
def scc():
    preorder = {}
    lowlink = {}
    seen = [False]*n
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(n):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in ns[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in ns[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans
comp = scc()
print(len(comp))
for item in reversed(comp):
    print(len(item), " ".join(map(str, item)))
### BUGGY CODE ###

N = int(input())
import collections
d = collections.Counter()
MOD = int(1e9 + 7)

max_i = 0
for a in map(int, input().split()):
  inv_bin = bin(a)[2:][::-1]
  for i, b in enumerate(inv_bin):
    if (b == '1'):
      d[i] += 1
  max_i = max(i, max_i)

ans = 0
for k, v in d.items():
  ans += (N - v) * v * (2 ** k) 
  ans %= MOD
print(ans)


### FIXED CODE ###

N = int(input())
import collections
d = collections.Counter()
MOD = int(1e9 + 7)

max_i = 0
for a in map(int, input().split()):
  inv_bin = bin(a)[2:][::-1]
  for i, b in enumerate(inv_bin):
    if (b == '1'):
      d[i] += 1
  max_i = max(i, max_i)

ans = 0
for k, v in d.items():
  ans += (N - v) * v * (2 ** k) 
  ans %= MOD
print(ans)
### BUGGY CODE ###

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

count = 0
if(n < 3):
    print(1)
else:
    for i in range(n-2):
        for j in range(i+1, n-1):
            if s[i] == s[j]:
                continue
            for k in range(j+1, n):
                if s[i] == s[k] or s[j] == s[k]:
                    continue
                if j-i != k-j:
                    count += 1
print(count)

### FIXED CODE ###

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

r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

discount = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        k = i + 2*(j-i)
        if k > n-1:
            break
        if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
            discount += 1

print(r_count*g_count*b_count-discount)
### BUGGY CODE ###

N = int(input())
d =  {}
a = list(map(int,input().split()))
for i in range(N):
    if a[i] not in d.keys():
        d[a[i]] = 1
    else:
        d[a[i]] +=1
ans = 0
for k,v in d.items():
    if v < k:
        ans += v
    else:
        ans += abs(v-k)
print(ans)


### FIXED CODE ###

from collections import Counter
inf = 10**10


N = int(input())
a = list(map(int,input().split()))
c = Counter(a)
ans = 0
for i,j in c.items():
    if j>=i:
        ans += j-i
    else:
        ans += j
print(ans)
### BUGGY CODE ###

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

r = []
g = []
b = []
for i in range(len(s)):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)
        
cnt = 0
for r_idx in r:
    for g_idx in g:
        j, i = max(r_idx, g_idx), min(r_idx, g_idx)
        for b_idx in b:
            if b_idx > j:
                if b_idx - j != j - i:
                    cnt += 1
            elif i > b_idx:
                if i - b_idx != j - i:
                    cnt += 1
            else:
                if j - b_idx != b_idx - i:
                    cnt += 1
print(cnt)

### FIXED CODE ###

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

r, g, b = set(), set(), set()
for i in range(len(s)):
    if s[i] == "R":
        r.add(i)
    elif s[i] == "G":
        g.add(i)
    else:
        b.add(i)
        
ans = len(r) * len(g) * len(b)
for r_idx in r:
    for g_idx in g:
        j, i = max(r_idx, g_idx), min(r_idx, g_idx)
        diff_ji = abs(j-i)
        cnt = 0
        for v in [j + diff_ji, i - diff_ji, (j + i) / 2]:
            if v in b:
                cnt += 1            
        ans -= cnt
print(ans)
### BUGGY CODE ###

import bisect as b
import sys
input=sys.stdin.readline
n=int(input())
ans=1
clist=[int(input())]
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist=[next]+clist
        ans+=1
    else:
        clist[pos-1]=next
print(ans)


### FIXED CODE ###

import bisect as b
from collections import deque
n=int(input())
ans=1
clist=deque([int(input())])
for i in range(n-1):
    next=int(input())
    pos=b.bisect_left(clist,next)
    if pos==0:
        clist.appendleft(next)
        ans+=1
    else:
        clist[pos-1]=next
print(ans)
### BUGGY CODE ###

import collections
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0]
    for i in range(len(S)):
        mod_all_bit.append(int_S % (10**(i+1)) % 2019)
    couter = {}
    for key in mod_all_bit:
        couter[key] = 0
    for key in mod_all_bit:
        couter[key] += 1
    ans = 0
    for key, val in couter.items():
        if val >= 2:
            ans += int(val * (val-1) * 0.5)
    return ans


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

def calc(a, b):
    return a**4+a**3*b+a**2*b**2+a*b**3+b**4

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

x = int(input())
div = make_divisors(x)
ans = 0
for yakusu in div:
    a = 0
    b = -yakusu
    while (a-b) * calc(a, b) <= x or b < 0:
        if abs((a-b) * calc(a, b)) == x:
            ans = (a, b)
            break
        else:
            a += 1
            b += 1
    if ans != 0: break

if ans[0]**5 - ans[1]**5 > 0:
    print(ans[0], ans[1])
else:
    print(ans[1], ans[0])

### FIXED CODE ###

x = int(input())

ans = 0
for a in range(-200, 200):
    for b in range(-200, 200):
        if a**5 - b**5 == x:
            ans = [a, b]
            break
    if ans != 0:
        break
print(ans[0], ans[1])
### BUGGY CODE ###

import copy
from functools import lru_cache
import math
def resolve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for k in range(K):
        #print("i", i)
        B = [0] * N
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        for i in range(1, N):
            B[i] += B[i - 1] 

        A = B[:]

        if min(A) == N:
            break

    print(" ".join(map(str, B)))

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import copy
from functools import lru_cache
import numpy as np
from numba import njit

#@njit
# @njit('(i8[::1],)', cache=True)
# def func(A):
#     N = len(A)
#     B = np.zeros_like(A)
#     for i in range(N):
#         l = max(0, i - A[i])
#         r = min(i + A[i], N-1)
#         B[l] += 1
#         if r+1 < N:
#             B[r+1] -= 1

#     B = np.cumsum(B)
#     return B

def resolve():
    N, K = map(int, input().split())
    A = np.array(list(map(int, input().split())))

    # N = 2 * 10**5
    # K = 2 * 10**5
    # A = np.array([0] *  N)

    @njit
    def func(A):
        #N = len(A)
        B = np.zeros_like(A)
        for i in range(N):
            l = max(0, i - A[i])
            r = min(i + A[i], N-1)
            B[l] += 1
            if r+1 < N:
                B[r+1] -= 1

        B = np.cumsum(B)
        return B

    for k in range(K):
        #print(k)
        A = func(A)
        if k >= 50:
            break

    print(" ".join(map(str, A)))

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

from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs(i, f, s):
    if visited[i]:
        return 1
    b = f + s
    visited[i] = True
    
    res = k - b
    s = f
    f = 1
    for v in E[i]:
        if visited[v]:
            continue
        res *= dfs(v, f, s)
        res %= p
        s += 1

    return res if res > 0 else 0

print(dfs(1, 0, 0))

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

n, k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n - 1)]
p = 10 ** 9 + 7

E = [[] for i in range(n + 1)]

for a, b in A:
    E[a].append(b)
    E[b].append(a)

visited = [False] * (n + 1)

def dfs(i, f, s):
    if visited[i]:
        return 1
    b = f + s
    visited[i] = True
    
    res = k - b
    s = f
    f = 1
    for v in E[i]:
        if visited[v]:
            continue
        res *= dfs(v, f, s)
        res %= p
        s += 1

    return res if res > 0 else 0

print(dfs(1, 0, 0) % p)
### BUGGY CODE ###

R,C,K=map(int,input().split())
RCV=[list(map(int,input().split())) for i in range(K)]
V=[[0]*(C+1) for i in range(R+1)]
for r,c,v in RCV:
    V[r][c]=v
d=[[[0]*4 for i in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        m=max(d[i][j+1])
        d[i+1][j+1][0]=m
        for k in range(3):
            d[i+1][j+1][k+1]=max(d[i+1][j][k+1],m+V[i+1][j+1],d[i+1][j][k]+V[i+1][j+1])
print(max(d[-1][-1]))

### FIXED CODE ###

import numpy as np
def main(R,C,K,RCV):
    V=np.zeros((R+1,C+1),dtype=np.int64)
    for i in range(K):
        V[RCV[i][0]][RCV[i][1]]=RCV[i][2]
    d=np.zeros((R+1,C+1,4),dtype=np.int64)
    for i in range(R):
        for j in range(C):
            m=max(d[i][j+1])
            d[i+1][j+1][0]=m
            for k in range(3):
                d[i+1][j+1][k+1]=max(d[i+1][j][k+1],m+V[i+1][j+1],d[i+1][j][k]+V[i+1][j+1])
    return max(d[-1][-1])
import sys
readline=sys.stdin.buffer.readline
read=sys.stdin.buffer.read
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')
    def cc_export(f,s):
        cc.export(f.__name__,s)(f)
        return njit(f)
    main=cc_export(main,(i8,i8,i8,i8[:,:],))
    cc.compile()
    exit()
R,C,K=np.array(readline().split(),dtype=np.int64)
RCV=np.array(read().split(),dtype=np.int64).reshape(K,3)
from my_module import main
print(main(R,C,K,RCV))
### BUGGY CODE ###

import collections

n=int(input())
ans=[0]*(n+1)
arr=[list(map(int,input().split())) for _ in range(n-1)]
arr=sorted(arr,key=lambda x:x[0])
s=set()
tmp=arr[0]
u,v,w=tmp[0],tmp[1],tmp[2]
s.add(u)
s.add(v)
if w%2==0:
  ans[u]=1
  ans[v]=1
elif w%2==1:
  ans[u]=1
  ans[v]=0
q=collections.deque()
cnt=1
cnt2=1
while 1:
  if cnt==n-1:
    break
  else:
    if cnt2<n-1:
      tmp=arr[cnt2]
      u,v,w=tmp[0],tmp[1],tmp[2]
    else:
      tmp=q.popleft()
      u,v,w=tmp[0],tmp[1],tmp[2]
    cnt2+=1
    if u in s:
      s.add(v)
      cnt+=1
      if w%2==0:
        ans[v]=ans[u]
      else:
        ans[v]=abs(ans[u]-1)
    elif v in s:
      s.add(u)
      cnt+=1
      if w%2==0:
        ans[u]=ans[v]
      else:
        ans[u]=abs(ans[v]-1)
    else:
      q.append([u,v,w])
for i in range(1,n+1):
  print(ans[i])

### FIXED CODE ###

import collections

n=int(input())
ans=[0]*(n+1)
tree=[[] for _ in range(n+1)]
for i in range(n-1):
  u,v,w=map(int,input().split())
  tree[u].append([v,w])
  tree[v].append([u,w])
q=collections.deque([1])
check=[False]*(n+1)
check[1]=True
tmp=tree[1][0]
if tmp[1]%2==0:
  ans[1]=1
  ans[tmp[0]]=1
else:
  ans[1]=1
  ans[tmp[0]]=0
while 1:
  if len(q)==0:
    break
  tmp=q.popleft()
  for i in range(len(tree[tmp])):
    v,w=tree[tmp][i][0],tree[tmp][i][1]
    if check[v]:
      continue
    else:
      check[v]=True
      if w%2==0:
        ans[v]=ans[tmp]
      else:
        ans[v]=abs(1-ans[tmp])
      q.append(v)
for i in range(1,n+1):
  print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = map(int, input().split())
Alist = list(map(int, input().split()))
import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


lcm_a = lcm_list(Alist)
mod = 10**9 + 7
ans = 0

for a in Alist:
    ans += (lcm_a // a)
    ans %= mod
print(ans % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = map(int, input().split())
Alist = list(map(int, input().split()))
import fractions
from functools import reduce


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


lcm_a = lcm_list(Alist)
mod = 10**9 + 7
ans = 0

for a in Alist:
    ans += (lcm_a // a)
print(ans % mod)
### BUGGY CODE ###

n,x,m = map(int,input().split())
mod = m
num = []
ans = 0
cnt = 0
ch = x
while True:
    if ch not in num:
        num.append(ch)
    else:
        st = ch #ループの開始している配列の初めの数字
        break
    ch *= ch
    ch %= mod
for i in range(len(num)):
    if num[i] == st:
        stnum = i #ループ開始の最初の配列のの番号
        #print("重なり始め =",stnum)
        break
else:
    stnum = len(num) - 1
if 0 in num:
    ans = sum(num[:n])
else:
    #print("len(num) =",len(num),"stnum =",stnum)
    if (len(num)-stnum) != 0:
        rest = (n-stnum)%(len(num)-stnum)
        sho = (n-stnum)//(len(num)-stnum)
        #print("rest =",rest,"sho =",sho)
    else:
        rest = n
        sho = 0
    if n <= stnum + 1:
        ans = sum(num[:n])
    else:
        ans = sum(num[:stnum]) + sum(num[stnum:stnum+rest]) + sum(num[stnum:])*sho
print(ans)

### FIXED CODE ###

n,x,m=map(int,input().split())
p=[0]*(m+1)
a=x
t=0
s=0
for i in range(2*m):
    if p[a]==1:
        p[a]=2
        break
    else:
        p[a]=1
        a=a**2%m
a=x
S=0
for i in range(2*m):
    if p[a]==1:
        s+=1
        S+=a
        a=a**2%m
    else:
        s+=1
        S+=a
        break
T=0
A=0
for i in range(2*m):
    a=a**2%m
    t+=1
    T+=a
    if p[a]==2:
        A=a
        break
a = x
if n <= s:
    ans=0
    for i in range(n):
        ans+=a
        a=a**2%m
    print(ans)
else:
    ans=S
    a=A
    n-=s
    ans+=(n//t)*T
    n=n%t
    for i in range(n):
        a=a**2%m
        ans+=a
    print(ans)
### BUGGY CODE ###

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

from collections import Counter

cnt = Counter(a)
b = set(a)

for i in range(n):
    ans = 0
    for j in b:
        if j == a[i]:
            c = cnt[j]-1
            ans += c*(c-1)//2
        else:
            c =cnt[j]
            ans += c*(c-1)//2
    print(ans)


### FIXED CODE ###

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

from collections import Counter

cnt = Counter(a)
b = set(a)
c = 0
for i in b:
    c += cnt[i]*(cnt[i]-1)//2

for i in a:
    print(c-cnt[i]+1)