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

import sys
from bisect import bisect_left 

def count_edge(a,b):
    if a>b:
        a,b=b,a
    edge[bisect_left(AB,[a,b])]+=1

N,M=map(int,input().split())
data=[[] for i in range(N+1)]
AB=[]
edge=[0]*M
count=[0]*(N+1)
for i in range(M):
    A,B=map(int,input().split())
    if A>B:
        A,B=B,A
    AB.append([A,B])
    data[A].append(B)
    data[B].append(A)
    count[A]+=1
AB.sort()

if M%2==1:
    print(-1)
    sys.exit()

parent=[0]*(N+1)
que=[1]
flag=[0]*(N+1)
flag[1]=1
parent[1]=1
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                parent[v]=u
                h.append(v)
    que=h

for i in range(1,N+1):
    if count[i]%2==0:
        continue
    else:
        count[i]+=1
        while True:
            j=parent[i]
            if i==j:
                break
            count_edge(i,j)
            if count[j]%2==1:
                count[j]+=1
                break
            i=j
            
for i in range(M):
    if edge[i]%2==0:
        print(*AB[i])
    else:
        print(*AB[i][::-1])

### FIXED CODE ###

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

def count_edge(a,b):
    global edge,AB
    if a>b:
        a,b=b,a
    edge[bisect_left(AB,(a,b))]+=1

def main():
    global edge,AB
    N,M=map(int,input().split())
    data=[[] for i in range(N+1)]
    AB=[]
    edge=[0]*M
    count=[0]*(N+1)
    for i in range(M):
        A,B=map(int,input().split())
        if A>B:
            A,B=B,A
        AB.append((A,B))
        data[A].append(B)
        data[B].append(A)
        count[A]^=1
    AB.sort()

    if M%2==1:
        print(-1)
        sys.exit()

    parent=[0]*(N+1)
    que=[1]
    parent[1]=1
    lsls=deque([])
    while que:
        h=[]
        for u in que:
            for v in data[u]:
                if parent[v]==0:
                    parent[v]=u
                    h.append(v)
                    if count[v]%2==1:
                        lsls.appendleft(v)
        que=h

    for i in lsls:
        if count[i]==0:
            continue
        else:
            count[i]=0
            while True:
                j=parent[i]
                if i==j:
                    break
                count_edge(i,j)
                if count[j]==1:
                    count[j]=0
                    break
                i=j
            
    for i in range(M):
        if edge[i]%2==0:
            print(*AB[i])
        else:
            print(*AB[i][::-1])
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
G = np.zeros((N, N), dtype=int)
for i in range(N):
    for j in range(i+1, N):
        G[i][j] = min(j - i, abs(X - i) + 1 + abs(Y - j))
for cnt in range(1, N):
    print(np.sum(G == cnt))


### FIXED CODE ###

N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = [0] * N
for i in range(N):
    for j in range(i+1, N):
        ans[ min(j - i, abs(X - i) + 1 + abs(Y - j))] += 1
for i in range(1, N):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
list = list(input())
lisr_r = list[::-1]
list_len = len(list)
ans = 0
count = 0

while count < n:
  if 'W' not in list or 'R' not in list:
    break

  w = list.index('W')
  r = lisr_r.index('R')

  if w > list_len - 1 - r:
    break

  list[w] = 'R'
  lisr_r[r] = 'W'

  ans += 1
  count += 1

print(ans)


### FIXED CODE ###

n = int(input())
list = input()
count_r = list.count('R')
ans = list[:count_r].count('W')

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

n,a,b,c = map(int,input().split())
now = [[a,b,c,[]]]
for _ in range(n):
  q = input()
  tmp = []
  if q == 'AB':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b+1,c,his+['B']])
      if b > 0:
        tmp.append([a+1,b-1,c,his+['A']])
  elif q == 'AC':
    for x in now:
      a,b,c,his = x
      if a > 0:
        tmp.append([a-1,b,c+1,his+['C']])
      if c > 0:
        tmp.append([a+1,b,c-1,his+['A']])
  else:
    for x in now:
      a,b,c,his = x
      if b > 0:
        tmp.append([a,b-1,c+1,his+['C']])
      if c > 0:
        tmp.append([a,b+1,c-1,his+['B']])
  if not tmp:
    print('No')
    exit()
  now = []
  now2 = []
  for d in range(3):
    m = max(tmp,key=lambda x:x[d])
    if m[:3] not in now2:
      now.append(m)
      now2.append(m[:3])
    m = min(tmp,key=lambda x:x[d])
    if m[:3] not in now2:
      now.append(m)
      now2.append(m[:3])
print('Yes')
ans = now[0][3]
for s in ans:
  print(s)

### FIXED CODE ###

#人生終わり
#解説解答
n,a,b,c = map(int,input().split())
if a + b + c == 0:
  print('No')
  exit()
elif a + b + c == 1:
  ans = []
  for _ in range(n):
    q = input()
    if q == 'AB':
      if a + b == 0:
        print('No')
        exit()
      a,b = b,a
      if a:
        ans.append('A')
      else:
        ans.append('B')
    elif q == 'BC':
      if b + c == 0:
        print('No')
        exit()
      b,c = c,b
      if b:
        ans.append('B')
      else:
        ans.append('C')
    else:
      if c + a == 0:
        print('No')
        exit()
      c,a = a,c
      if a:
        ans.append('A')
      else:
        ans.append('C')
  print('Yes')
  for x in ans:
    print(x)
  exit()
p = []
for _ in range(n):
  p.append(input())
if a + b == 0 and p[0] == 'AB':
    print('No')
    exit()
if b + c == 0 and p[0] == 'BC':
    print('No')
    exit()
if a + c == 0 and p[0] == 'AC':
    print('No')
    exit()
print('Yes')
for i in range(n):
  if p[i] == 'AB':
    if a == 0:
      a += 1
      b -= 1
      print('A')
    elif b == 0:
      a -= 1
      b += 1
      print('B')
    elif i != n-1:
      if p[i+1] == 'BC':
        a -= 1
        b += 1
        print('B')
      else:
        a += 1
        b -= 1
        print('A')
    else:
      a += 1
      b -= 1
      print('A')
  elif p[i] == 'BC':
    if b == 0:
      b += 1
      c -= 1
      print('B')
    elif c == 0:
      b -= 1
      c += 1
      print('C')
    elif i != n-1:
      if p[i+1] == 'AC':
        b -= 1
        c += 1
        print('C')
      else:
        b += 1
        c -= 1
        print('B')
    else:
      b += 1
      c -= 1
      print('B')
  else:
    if a == 0:
      a += 1
      c -= 1
      print('A')
    elif c == 0:
      a -= 1
      c += 1
      print('C')
    elif i != n-1:
      if p[i+1] == 'BC':
        a -= 1
        c += 1
        print('C')
      else:
        a += 1
        c -= 1
        print('A')
    else:
      a += 1
      c -= 1
      print('A')
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

K = int(input())

a = 0
ans = -1

for i in range(K):

    a += 7 * 10**i

    if a % K == 0:
        ans = i+1
        break

print(ans)

### FIXED CODE ###

k = int(input())
if k==1 or k==7:
  print(1)
elif k%2==0:
  print(-1)
else:
  cnt = 1
  pre = 7
  while(True):
    surp = (pre*10+7)%k
    cnt += 1
    if surp==0:
      break
    if cnt>1000000:
      cnt = -1
      break
    pre = surp
  print(cnt)
### BUGGY CODE ###

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

ans = 0
for i in range(1, n+1):
    _ans = (a*i//b) - a*(i//b)
    ans = max(ans, _ans)

print(ans)


### FIXED CODE ###

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

if b<=n:
    i = b-1
    ans = (a*i//b) - a*(i//b)
else:
    i = n
    ans = (a*i//b) - a*(i//b)

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

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

dict = {}

for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      key = S[i]+S[j]+S[k]
      dict[key] = 0
print(len(dict))

### FIXED CODE ###

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

count = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      pas = (str(i),str(j),str(k))
      key = 0
      for c in S:
        if c == pas[key]:
          key += 1
          if key ==3:
            count +=1
            break
print(count)
### BUGGY CODE ###

import sys
from collections import deque, Counter

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, a = na()
x = na()
x = [0] + x
dp = [[[0] * (50 * n + 1) for i in range(n+1)] for j in range(n+1)]

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(50 * n + 1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
            else:
                dp[j][k][s] = 0
print(sum([dp[n][k][k * a] for k in range(1, n+1)]))



### FIXED CODE ###

import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, a = na()
x = na()
x = [0] + x
dp = [[[0] * (50 * n + 1) for i in range(n+1)] for j in range(n+1)]

for j in range(n + 1):
    for k in range(j + 1):
        for s in range(50 * n + 1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j]:
                dp[j][k][s] = dp[j - 1][k][s]
            elif j >= 1 and k >= 1 and s >= x[j]:
                dp[j][k][s] = dp[j - 1][k][s] + dp[j - 1][k - 1][s - x[j]]
            else:
                dp[j][k][s] = 0
print(sum([dp[n][k][k * a] for k in range(1, n+1)]))
### BUGGY CODE ###

def main():
  AC = 0
  WA = 0
  
  N,M = map(int, input().split())
  
  Q = [] 
  
  P = [0] * M
  S = [0] * M
  
  for i in range(M):
    _p, _s = input().split()
    P[i] = int(_p)
    S[i] = _s
    
  for i,s in enumerate(S):
    if s == 'AC' and P[i] not in Q:
      AC += 1
      for j in range(i):
        if P[j] == P[i] and S[j] == 'WA':
          WA += 1
      Q.append(P[i])
  
  print(AC, WA)
  return 0

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  AC = 0
  WA = 0
  
  solving = {}
  solved = {}
  
  N,M = map(int, input().split())
  
  for i in range(M):
    p, s = input().split()
    if p in solved:
      continue
    elif s == 'WA':
      if p in solving:
        _wa = solving[p]
        solving[p] = _wa + 1
      else:
        solving[p] = 1
    else:
      AC += 1
      if p in solving:
      	WA += solving[p]
      solved[p] = True
  
  print(AC, WA)
  return 0
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

f_list = [0 for i in range(N+1)]
f_list[0] = 1
for i in range(1, N+1):
    f_list[i] = f_list[i-1]*i

def c(n):
    return f_list[n]//f_list[n-2]//2

m = Counter(A)
s = 0
for x, y in m.items():
    if y != 1:
        s += c(y)
for a in A:
    print(s - (m[a] - 1))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]

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

m = Counter(A)
s = 0
for x, y in m.items():
    if y != 1:
        s += c(y)
for a in A:
    print(s - (m[a] - 1))
### BUGGY CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)

root = 1
for j in g:
    if len(g[j]) == 1:
        root = j
        break
root = 1
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

### FIXED CODE ###

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 6)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



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

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)
### BUGGY CODE ###

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

def facto(x):

    ret = 1
    for i in range(2, x + 1):
        ret *= i
    return ret

def C(x, y):
    return facto(x) // facto(x - y) // facto(y)

def calc(n, k, t):
    return C(n - k + 1, t) * C(k - 1, t - 1) % (10 ** 9 + 7)

for i in range(1, k + 1):
    print(calc(n, k, i))


### FIXED CODE ###

import math

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

ans_list = []

def C(x, y):
    return math.factorial(x) // math.factorial(x - y) // math.factorial(y)

def calc(n, k, t):
    return C(n - k + 1, t) * C(k - 1, t - 1) % (10 ** 9 + 7)

for i in range(1, k + 1):
    
    if n - k <= 0:
        if len(ans_list) == 0:
            ans_list.append(1)
        else:
            ans_list.append(0)
    else:
        if i > (n - k + 1):
            if len(ans_list) == 0:
                ans_list.append(1)
            else:
                ans_list.append(0)
        else:
            ans_list.append(calc(n, k, i))

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

def main():
  s = input()
  t = input()
  n = len(s)
  m = len(t)
  dp = [[0]*(m+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(m):
      if s[i] == t[j]:
        dp[i+1][j+1] = dp[i][j] + 1
      else:
        dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
  i,j = n,m
  ans = ""
  while i and j:
    if dp[i][j] == dp[i-1][j]:
      i -= 1
    elif dp[i][j] == dp[i][j-1]:
      j -= 1
    else:
      i -= 1
      j -= 1
      ans += s[i]
  print(ans[::-1])

if __name__ == "__main__":
  main()

### FIXED CODE ###

s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])
i,j = n,m
ans = ""
while i and j:
  if dp[i][j] == dp[i-1][j]:
    i -= 1
  elif dp[i][j] == dp[i][j-1]:
    j -= 1
  else:
    i -= 1
    j -= 1
    ans += s[i]
print(ans[::-1])
### BUGGY CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
mx = max(x)
mx = max(mx,a)
dp = [[[0]*(n*mx+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*mx+1):
            if k<x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j>0 and k>=x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
ans = 0
for i in range(n+1):
        ans += dp[n][i][a*i]
print(ans-1)

### FIXED CODE ###

n,a = map(int,input().split())
x = list(map(int,input().split()))
mx = max(x)
mx = max(mx,a)
dp = [[[0]*(n*mx+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        for k in range(n*mx+1):
            if k<x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]
            elif j>0 and k>=x[i-1]:
                dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-1][k-x[i-1]]
ans = 0
for i in range(n+1):
        ans += dp[n][i][a*i]
print(ans-1)
### BUGGY CODE ###

#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters.append((INPUT2[0], INPUT2[1]))

Parameters = sorted(Parameters, key=lambda x: x[1], reverse=True)

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    kindset = set(kind)
    for i in range(len(List)-K):
        if List[K+i][0] not in kindset:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    for i in range(K):
        testkind = List[K-1-i][0]
        kind.pop(K-1-i)
        if testkind in kind:
            result = K-1-i
            break
    return result

for i in range(K):
    kind.append(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)

for t in Parameters:
    for i in range(K):
        kind.append(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

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

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
counter = 0
r = N // R + 1
g = N // G + 1
for s in range(r):
  for t in range(g):
    u = N - R*s - G*t
    if u >= 0 and u % B == 0:
      counter += 1
print(counter)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
counter = 0
for s in range(n+1):
  for t in range(n-s+1):
    u = n - r*s - g*t
    if u >= 0 and u % b == 0:
      counter += 1
print(counter)
### BUGGY CODE ###

K, S = list(map(int, input().split()))
count = 0
for x in range(0, K + 1):
    for y in range(0, K + 1):
        for z in range(0, K + 1):
            if x + y + z == S:
                count+=1
print(count)

### FIXED CODE ###

K, S = list(map(int, input().split()))
count = 0
for x in range(0, K + 1):
    for y in range(0, K + 1):
        z = S - x - y
        if 0 <= z <= K:
            count+=1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
for i in range(60):
  n = len([x for x in A if x % 2 ==1])
  A = [x//2 for x in A]
  t = 2**i
  res += n*(N-n)*t
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)
### BUGGY CODE ###

import numpy as np
def serach(target, array):
    l, r = -1, len(array)
    while r - l > 1:
        m = (l+r)//2
        if array[m] < target:
            l = m
        else:
            r = m
    return l, r

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

BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)

for b, c in BC:
    A.sort()
    l, r = serach(c, A)
    if r <= 0:
        break
    b = min(b, len(A[:r]))
    A[:b] = c

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
for i in range(M):
    b, c = map(int, input().split())
    A.append([b, c])

total = 0
D = []
A = sorted(A, key=lambda x:x[1], reverse=True)
for b, c in A:
    if len(D) >= N:
        break
    D.extend([c]*b)
print(sum(D[:N]))
### BUGGY CODE ###

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

ans=3*(10**9)
for i in range(N-1):
  l=(numpy.cumsum(A))[i]
  D=abs(l-(sum(A)-l))
  if ans > D:
    ans=D

print(ans) 

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
 
import numpy as np

def getNearestValue(list, num):
  idx = np.abs(np.asarray(list) - num).argmin()
  return list[idx]

a=(np.cumsum(A))
l=getNearestValue(a, sum(A)/2)

ans=abs(sum(A)-2*l)
print(ans)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
t = [1 if S[j:j+2] == "AC" else 0 for j in range(N)]
for i in range(Q):
  l, r = list(map(int, input().split()))
  print(int(sum(t[l-1:r-1])))

### FIXED CODE ###

import numpy as np
N, Q = list(map(int, input().split()))
S = input()
t = [0] * N
for j in range(1, N):
  t[j] = t[j-1] + 1 if S[j-1:j+1] == "AC" else t[j-1]
for i in range(Q):
  l, r = list(map(int, input().split()))
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
amount = [0]*n

for i in range(n):
    amount[i] = a.count(i+1)

for j in range(n):
    ans = 0
    for k in range(n):
        ans += amount[k]*(amount[k]-1)//2
    ans -= amount[a[j]-1] -1
    print(ans)

### FIXED CODE ###

import numpy as np
def main():
    from collections import Counter
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    c = Counter(a)
    for i in range(n):
        ans += c[i+1]*(c[i+1]-1)//2
    for j in range(n):
        print(ans - c[a[j]] + 1)
if __name__ == '__main__':
    main()