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

# -*- coding: utf-8 -*-

from functools import lru_cache
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap



def slv(N, A):
    ca = Counter(A)
    s = [[ca[1], ca[2], ca[3]]]
    o = []
    while s:
        c1, c2, c3 = s.pop()
        o.append((c1, c2, c3))
        if c1 > 0:
            s.append((c1-1, c2, c3))
        if c2 > 0:
            s.append((c1+1, c2-1, c3))
        if c3 > 0:
            s.append((c1, c2+1, c3-1))

    memo = defaultdict(lambda: defaultdict(dict))
    memo[0][0][0] = 0
    while o:
        c1, c2, c3 = o.pop()
        if c1 == c2 == c3 == 0:
            continue
        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        if c1 >0:
            ret += memo[c1-1][c2][c3] * p1 / ip0
        if c2 > 0:
            ret += memo[c1+1][c2-1][c3] * p2 / ip0
        if c3 > 0:
            ret += memo[c1][c2+1][c3-1] * p3 / ip0
        memo[c1][c2][c3] = ret


    return memo[ca[1]][ca[2]][ca[3]]

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))



if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# 入力
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

# DPテーブルを用意
dp = [float("inf")] * N
# 初期値をセット
dp[0] = 0

# 足場0から順次最小コストを決定する
for i in range(1, N):
    # for j in range(1, K+1):
        # if i + j < N:
            # dp[i+j] = min(dp[i+j], (dp[i] + abs(H[i] - H[i+j])))
    dp[i] = min([dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, min(K+1, i+1)) if i-j >= 0])

# 足場NのインデックスはN-1
print(dp[N-1])

### FIXED CODE ###

import numpy as np

# 入力
N, K = map(int, input().split())
H = np.array([int(i) for i in input().split()])

# ndarray型のDPテーブルを生成
dp = np.zeros(N, dtype=int)
# 初期値をセット
dp[0] = 0

# 各足場へたどり着く最小コストを調べる
for i in range(1, N):
    s = max(0, i-K)
    dp[i] = min(dp[s:i] + np.abs(H[i] - H[s:i])) # iより前の足場のコストに足す

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

# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    cnt = 0
    min_cnt = float("inf")
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            cnt += 1
        else:  # brackets[i] == ")"
            cnt -= 1
            min_cnt = min(min_cnt, cnt)
    
    return cnt, min_cnt

#-----
tmp_cnt_plus  = []
tmp_cnt_minus = []

for S in S_list:
    cnt, min_cnt = count_brackets(S)
    
    if cnt >= 0:
        tmp_cnt_plus.append( (cnt, min_cnt) )
    else:  # cnt < 0
        tmp_cnt_minus.append( (cnt, min_cnt) )


tmp_cnt_plus.sort(key=lambda x: -x[1])
tmp_cnt_minus.sort(key=lambda x: -(x[0]-x[1]) )


sum_bracket = 0
flag = True

for cnt, min_cnt in (tmp_cnt_plus + tmp_cnt_minus):
    if (sum_bracket + min_cnt) < 0:
        flag = False
        break
    
    sum_bracket += cnt


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input().strip())
S_list = [input().strip() for _ in range(N)]
#-----

def count_brackets(brackets):
    L = R = 0
    L_rev = R_rev = 0
    max_R = -float("inf")
    max_L = -float("inf")
    
    
    for i in range(len(brackets)):
        if brackets[i] == "(":
            L += 1
        else:  # brackets[i] == ")"
            R += 1
            max_R = max(max_R, R - L)
        
        if brackets[len(brackets)-1-i] == "(":
            L_rev += 1
            max_L = max(max_L, L_rev - R_rev)
        else:  # brackets[len(brackets)-1-i] == ")"
            R_rev += 1
    
    if max_L < 0: max_L = 0
    if max_R < 0: max_R = 0
    
    return max_L, max_R


tmp_cnt1 = []  #  the number of "("  >=  the number of ")"
tmp_cnt2 = []  #  the number of "("  <   the number of ")"

for S in S_list:
    cnt_L,cnt_R = count_brackets(S)

    if cnt_L == cnt_R == 0:
        continue
    
    if cnt_L >= cnt_R:
        tmp_cnt1.append( (cnt_L,cnt_R) )
    else:
        tmp_cnt2.append( (cnt_L,cnt_R) )


tmp_cnt1.sort(key=lambda x: x[1])
tmp_cnt2.sort(key=lambda x: -x[0])


sum_bracket = 0
flag = True

for cnt_L,cnt_R in (tmp_cnt1 + tmp_cnt2):
    sum_bracket -= cnt_R
    if sum_bracket < 0:  flag = False
    
    sum_bracket += cnt_L
    if sum_bracket < 0:  flag = False
    
    if flag == False:
        break


if (sum_bracket == 0) and flag:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

memory = {}

def count_answer(x,y):
    count = 0
    actions = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
    # print("x,y:",x,y)
    for action0 in range(4):
        next_x = x + actions[action0][0]
        next_y = y + actions[action0][1]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif [next_x,next_y] in reach_position:
            pass
        elif S_[next_x,next_y] == ".":
            reach_position.append([next_x,next_y])
            for action in range(4):
                next_next_x = next_x +actions[action][0]
                next_next_y = next_y +actions[action][1]
                # print(next_next_x,next_next_y)
                if next_next_x == -1 or next_next_y == -1:
                    pass
                elif next_next_x >= H or next_next_y >= W:
                    pass
                elif S_[next_next_x,next_next_y] == "#":

                    memory_key = str(next_next_x)+str(next_next_y)
                    if memory_key in memory.keys():
                        tem_poss = memory[memory_key]
                    else:
                        tem_poss = count_answer(next_next_x,next_next_y)
                    for tem_pos in tem_poss:
                        if tem_pos in reach_position:
                            pass
                        else:
                            reach_position.append(tem_pos)
                    # reach_position = reach_position and tem_poss
    memory[str(x)+str(y)] = reach_position
    # memory[[x,y]] = reach_position
    return reach_position

answer = 0
for i in range(H):
    for j in range(W):
        if S_[i,j] == "#":
            reach_position = []
            reach_position = count_answer(i,j)
            answer += len(reach_position)
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
d = defaultdict(list)

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    d[h-1].append(w-1)
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

maxi = 0
for i in hlist:
    for j in wlist:
        ans = maxh + maxw
        if j in d[i]:
            ans -= 1
        maxi = max(maxi,ans)
        # print(maxi)
print(maxi)


### FIXED CODE ###

import sys
input = sys.stdin.readline
l = set()

sh,sw,m = map(int,input().split())
H = [0]*sh
W = [0]*sw
for i in range(m):
    h,w = map(int,input().split())
    l.add((h-1,w-1))
    H[h-1] += 1
    W[w-1] += 1

maxh = max(H)
maxw = max(W)
# print(H,W)
# print(maxh,maxw)

hlist = []
wlist = []

for i in range(sh):
    if H[i] == maxh:
        hlist.append(i)
for j in range(sw):
    if W[j] == maxw:
        wlist.append(j)
# print(hlist,wlist)

if len(hlist)*len(wlist) > m:
    print(maxh+maxw)
    exit()

ans = maxh+maxw-1
for i in hlist:
    for j in wlist:
        if (i,j) not in l:
            print(ans+1)
            exit()
print(ans)
### BUGGY CODE ###

# coding: utf-8
S = input()
Q = int(input())

def pop(s, rev, f, c):
    ret = s
    if rev == 1:
        if f == '1':
            ret = c + s
        else:
            ret = s + c
    else:
        if f == '1':
            ret = s + c
        else:
            ret = c + s
    return ret


rev = 1
for _ in range(Q):
    que = input().split()
    if que[0] == '1':
        rev *= -1
        continue
    if que[0] == '2':
        S = pop(S, rev, *que[1:])
print(S[::rev])

### FIXED CODE ###

# coding: utf-8
S = input().split()
Q = int(input())

def pop(left, right, rev, f, c):
    if rev == 1:
        if f == '1':
            left.append(c)
        else:
            right.append(c)
    else:
        if f == '1':
            right.append(c)
        else:
            left.append(c)
    return left, right


left, right = [], []
rev = 1
for _ in range(Q):
    que = input().split()
    if que[0] == '1':
        rev *= -1
        continue
    if que[0] == '2':
        left, right = pop(left, right, rev, *que[1:])
print(''.join(left[::-1]+S+right)[::rev])
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)
for _ in range(M):
    B, C = map(int, input().split())
    for _ in range(B):
        A_min = A[0]
        if A_min >= C:
            continue
        heapq.heappop(A)
        heapq.heappush(A, C)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
B_C = []
for _ in range(M):
    B, C = map(int, input().split())
    B_C.append((C, B))
B_C = sorted(B_C, reverse=True)
Cs = []
rem = N
for c, b in B_C:
    if rem >= b:
        Cs += [c]*b
        rem -= b
    else:
        Cs += [c]*rem
        break
ans = sum(sorted(A+Cs, reverse=True)[:N])
print(ans)
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
kotei=k
ans=0
cnt=0

if kotei>=sum(a):
  cnt+=len(a)
  ans=max(ans,cnt)
else:
  x=kotei
  i=0
  while x>=0:
    x-=a[i]
    i+=1
    cnt+=1
  ans=max(ans,cnt-1)

for j in range(m):
  kotei-=b[j]
  if kotei<0:
    break
  cnt=j+1
  if kotei>=sum(a):
    cnt+=len(a)
    ans=max(ans,cnt)
    continue
  else:
    x=kotei
    i=0
    while x>=0:
      x-=a[i]
      i+=1
      cnt+=1
    ans=max(ans,cnt-1)
print(ans)


### FIXED CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0

A,B=[0],[0]
for i in range(n):
  A.append(a[i]+A[i])
for i in range(m):
  B.append(b[i]+B[i])

for j in range(n+1):
  K=k-A[j]
  if K<0:
    break
  left=0
  right=m+1
  while left<right:
    mid=(left+right)//2
    if B[mid]>K:
      right=mid
    else:
      left=mid+1
  ans=max(ans,j+left-1)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    count = 0
    flg = 0
    for j in range(l-1, r, 2):
        if s[j] =="A":
            if s[j+1] == "C":
                count +=1
            elif s[j+1] == "A": 
                flg = 1
        elif s[j] =="T" or s[j] =="G":
            if s[j+1] == "A": 
                flg = 1
        elif s[j] == "C" and flg ==1:
                count +=1
                flg = 0
        else:
            pass
    print(count)

### FIXED CODE ###

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

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

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

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

for i in range(1, n+1):
    count = A.count(i)
    print(count)


### FIXED CODE ###

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

# m = 0
# t = 0

# for i in range(1, n):
#     count = A.count(i)
#     print(count)
#     m += count
#     t = i
#     if m == n - 1:
#         break
# for _ in range(t, n):
#     print(0)

B = [0] * n
for i in A:
    B[i-1] += 1
for i in B:
    print(i)
### BUGGY CODE ###

from numpy import*;B=searchsorted;a,b=loadtxt(open(0),int,skiprows=1);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)

### FIXED CODE ###

from numpy import*;B=searchsorted;a,b=split(int32(open(0).read().split()[1:]),2);c=0;l=2**29
while l:h=l;l//=2;y=sort(hstack((b%h-h,b%h)));c+=sum(B(y,h-a%h)-B(y,l-a%h))%2*l
print(c)
### BUGGY CODE ###

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

max_ = 0
for i in range(n):
    count = 0
    cur_k = 0
    is_zero = False
    for c in s[i:]:
        if len(s[i:]) < max_:
            break
        if c == '1':
            count += 1
            is_zero = False
        else:
            if is_zero:
                count += 1
            elif cur_k < k:
                cur_k += 1
                count += 1
                is_zero = True
            else:
                break
    if count > max_:
        max_ = count
print(max_)


### FIXED CODE ###

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

change_points = [i for i in range(n) if i == 0 or s[i-1] != s[i]]
change_points.append(n)
max_ = 0
for i, p in enumerate(change_points):
    if i == len(change_points) - 1:
        continue
    if s[p] == '0':
        if i == 0:
            idx = min(i + 2 * k, len(change_points) - 1)
            tmp = change_points[idx] - p
        else:
            continue
    else:
        idx = min(i + 2 * k + 1, len(change_points) - 1)
        tmp = change_points[idx] - p
    if tmp > max_:
        max_ = tmp

print(max_)
### BUGGY CODE ###

N, W = (int(x) for x in input().split())
A = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
  w, v = A[i]
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j >= w:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j - w] + v) 
print(dp[N][W])

### FIXED CODE ###

N, W = (int(x) for x in input().split())
A = [[int(x) for x in input().split()] for i in range(N)]
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
  w, v = A[i]
  for j in range(W+1):
    dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    if j >= w:
      dp[i+1][j] = max(dp[i+1][j], dp[i][j - w] + v) 
print(dp[N][W])
### BUGGY CODE ###

N,K=list(map(int, input().split()))
ans = N
if N%K==0:
  print(0)
  exit()
while True:
    N = abs(N-K)
    if N < ans:
        ans=N
    elif N == ans or ans== 0:
        break
print(ans)

### FIXED CODE ###

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

ans = N
if N%K==0 :
  print(0)
else:
  N = N%K
  while True:
      N = abs(N-K)
      if N < ans:
          ans=N
      elif N == ans or ans== 0:
          break
  print(ans)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        alt = d[i][j] 
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        alt += 1
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


if __name__ == "__main__":
    main()

### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=tf-8
#

"""
"""

from collections import defaultdict
import bisect
from itertools import product
from collections import deque

import sys
input = sys.stdin.readline

def solve(h,w,ch,cw,dh,dw,s):
    d = [[10**7]*w for _ in range(h)]
    d[ch][cw] = 0
    dis0 = [(1,0),(0,1),(-1,0),(0,-1)]
    dis1 = [(i,j) for i,j in product(range(-2,3),range(-2,3)) if 1 < abs(i)+abs(j)]
    Q = deque([(ch,cw)])
    ans = -1
    while Q:
        pos1 = Q.pop()
        i, j = pos1
        if i == dh and j==dw:
            ans = d[dh][dw]
            break
        for pos2 in [(i+a,j+b) for a,b in dis0 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j] 
            if d[k][l] > alt:
                d[k][l] = alt
                Q.append((k,l))
        for pos2 in [(i+a,j+b) for a,b in dis1 if 0 <= i+a < h and 0 <= j+b <w and s[i+a][j+b]=="."]:
            k, l = pos2
            alt = d[i][j]+1
            if d[k][l] > alt:
                d[k][l] = alt
                Q.appendleft((k,l))
    print(ans)



def main():
    h, w = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1
    s = []
    for _ in range(h):
        s.append(list(input().rstrip()))
    solve(h,w,ch,cw,dh,dw,s)


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

n,k=map(int,input().split())
p=list(map(int,input().split()))
for i in range(n):
    p[i]=(p[i]+1)/2
ans=0.0
for i in range(n-k+1):
    if(ans<sum(p[i:i+k])):
        ans=sum(p[i:i+k])
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
pp=[]
su=0
for i in range(n):#累積和
    if i<k:
        su+=p[i]
    else:
        pp.append(su)
        su=su-p[i-k]+p[i]
pp.append(su)
ans=0.0
for i in range(len(pp)):
    j=(pp[i]+k)/2
    if ans<j:
        ans=j
print(ans)
### BUGGY CODE ###

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

P = []
Y = []

for i in range(m):
    p, y = map(int, input().split())
    P.append(p)
    Y.append(y)

C = zip(P, Y)
C = sorted(C)
P_, Y_ = zip(*C)
P_ = list(P_)
Y_ = list(Y_)

for i in range(m):
    begin = P[i]
    end = Y_[P_.index(begin):].index(Y[i])+1
    print('{:06}{:06}'.format(begin, end))

### FIXED CODE ###

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

P = []
Y = []
I = []
for i in range(m):
    a, b = map(int, input().split())
    P.append(a)
    Y.append(b)
    I.append(i)

Z = zip(P, Y, I)
Z = sorted(Z)
P, Y, I = zip(*Z)

N = []
c = P[0]
d = 1
for i in range(m):
    if c == P[i]:
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1
    else:
        c = P[i]
        d = 1
        N.append("{0:06d}{1:06d}".format(c, d))
        d += 1

Z = zip(I, N)
Z = sorted(Z)
I, N = zip(*Z)
for i in N:
    print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m,k=map(int,input().split())

L=[[] for i in range(n)]
U=[[] for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	L[a-1].append(b-1)
	L[b-1].append(a-1)
for i in range(k):
	c,d=map(int,input().split())
	U[c-1].append(d-1)
	U[d-1].append(c-1)
	
S=[[] for i in range(n)]
D=[0]*n

def dfs(n):
	D[n]=1
	T.append(n)
	for np in L[n]:
		if D[np]!=1:
			dfs(np)
			
for i in range(n):
	if D[i]==1:
	    continue
	T=[]
	dfs(i)
	for t in T:
		S[t]=T[:]
		S[t].remove(t)
		
R=[0]*n
for i in range(n):
	R[i]=len(S[i])-len(L[i])-len(set(S[i])&set(U[i]))
print(*R)

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())

F=[set() for i in range(n)]
B=[set() for i in range(n)]
for i in range(m):
	a,b=map(int,input().split())
	a,b=a-1,b-1
	F[a].add(b)
	F[b].add(a)
for i in range(k):
	c,d=map(int,input().split())
	c,d=c-1,d-1
	B[c].add(d)
	B[d].add(c)
	
T=[set() for i in range(n)]
D=[0]*n
R=[0]*n

for i in range(n):
    if D[i]:
        continue
    que=deque([])
    que.append(i)
    S=set()
    S.add(i)
    while que:
        p=que.popleft()
        for np in F[p]:
            if D[np]!=1:
                que.append(np)
                S.add(np)
                D[np]=1
    for s in S:
        R[s]=len(S)-len(F[s])-len(S&B[s])-1

print(*R)
### BUGGY CODE ###

N= int(input())
A = list(map(int, input().split()))
B=[0]*N
C=0
for i in range(N):
    B[i]=A.count(i+1)
    C = C + B[i] * (B[i] - 1) / 2
for i in range(N):
    print(int(C-(B[A[i]-1])+1))

### FIXED CODE ###

import math
import collections

def cmb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
N = int(input())
M = input().split()

total = 0
count = collections.Counter(M)

for i in count.values():
    if i >= 2:
        total += cmb(i, 2)
    
for j in M:
    print(total - (count[j]-1))