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

from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = {}
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= {i} | conn
            conns.update({i: conn})
            for j in conn:
                conns.update({j: conn})

    print(' '.join([str(len(conns[i] - graph_f[i] - graph_b[i]) - 1) for i in range(n)]))


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    u = UnionFind(n)
    f_cnt = [0] * n
    b_cnt = [0] * n

    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
        f_cnt[a - 1] += 1
        f_cnt[b - 1] += 1

    for _ in range(k):
        c, d = map(int, input().split())
        if u.same(c - 1, d - 1):
            b_cnt[c - 1] += 1
            b_cnt[d - 1] += 1

    print(*[(u.size(i) - f_cnt[i] - b_cnt[i] - 1) for i in range(n)])
### BUGGY CODE ###

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  d = [float('inf')]*n
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != float('inf') and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = -float('inf')
      if i == n-1:
        temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  x, y = x-1, y-1
  z = (z-p)*(-1)
  es.append([x, y, z])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def find_negative_loop(s,n,w,es):
  # s: start
  # n: number of nodes
  # w: number of edges
  # es[i]: from, to, cost
  
  # d: shortest dist of s -> i
  inf = float('inf')
  d = [inf for _ in range(n)]
  d[s] = 0
  for i in range(2*n):
    for j in range(w):
      p, q, r = es[j]
      if d[p] != inf and (d[q] > d[p] + r):
        d[q] = d[p] + r
        if i >= n:
          d[q] = (-1)*inf
    if i == n-1:
      temp = d[-1]
  return temp, d[-1]
         

n, w, p = map(int, input().split())
es = []
for i in range(w):
  x, y, z = map(int, input().split())
  es.append([x-1, y-1, (z-p)*(-1)])
  
temp, d = find_negative_loop(0, n, w ,es)
if temp == d:
  print(min(0, d)*(-1))
else:
  print('-1')
### BUGGY CODE ###

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

Pow=[pow(inverse[2],i,mod) for i in range(N+1)]

def func(n):
    if n%2==0:
        return (-g1[n]*g2[n//2]*Pow[n//2])%mod
    else:
        return 0

import sys

sys.setrecursionlimit(10**4)

N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

def dfs(v,pv):
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        if nv!=pv:
            dfs(nv,v)
            merged=[0]*(sz[v]+sz[nv]+1)
            for i in range(sz[v]+1):
                for j in range(sz[nv]+1):
                    merged[i+j] +=dp[v][i]*dp[nv][j]
                    merged[i+j]%=mod
            sz[v]+=sz[nv]
            dp[v] =merged
    dp[v][0]=(sum(func(k)*dp[v][k] for k in range(1,sz[v]+1)))%mod

dfs(0,-1)

print((-dp[0][0])%mod)

### FIXED CODE ###

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys

sys.setrecursionlimit(10**4)

N=int(input())
edge=[[] for i in range(N)]
parent=[0]*N
deg=[1]*N
deg[0]=0
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


def prv(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            parent[nv]=v
            prv(nv,v)

prv(0,-1)

for i in range(N):
    new=[]
    for v in edge[i]:
        if v!=parent[i]:
            new.append(v)
    edge[i]=new


from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

for v in ans[::-1]:
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        merged=[0]*(sz[v]+sz[nv]+1)
        for i in range(sz[v]+1):
            for j in range(sz[nv]+1):
                merged[i+j]=(merged[i+j]+dp[v][i]*dp[nv][j])%mod
        sz[v]+=sz[nv]
        dp[v] =merged
    for k in range(1,sz[v]+1):
        dp[v][0]=(dp[v][0]-(g1[k]*g2[k//2])%mod*((k+1)%2)*dp[v][k])%mod

print((-dp[0][0]*pow(inverse[2],N//2,mod))%mod)
### BUGGY CODE ###

S=input()
N=len(S)


T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    d[r]+=1

ans=0
for i in d:
    ans+=((i*(i-1))//2)

print(ans)

### FIXED CODE ###

S=input()
N=len(S)
#「連続する区間」についての問題では、”累積和的なもの”をとるのが定石である。
#Sの連続する区間が、右からa文字分から、右からb文字分を取り除いたものであるとき
#その区間の整数が2019の倍数になるということは、s[a]とs[b]を2019で割ったあまりが等しい
#十分条件であることは分かったが、必要条件であるのか
#結論として必要条件でもある
#なぜなら2019と10は互いに素であるからである。

T=[]
T.append(0)
tmp=""
d=[0 for _ in range(2019)]
d[0]=1
r=0
t=1
for i in range(N):
    s=S[N-1-i]
    r+=int(s)*t
    r%=2019
    t*=10
    t%=2019 
    d[r]+=1

ans=0

print(sum(i*(i-1)//2 for i in d))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    limit = 10**18
    N = int(input())
    A = list(map(int, input().split()))
    assert N == len(A)
    answer = 1
    for i in A:
        answer *= i
    print(answer) if answer <= limit else print("-1")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    limit = 10**18
    N = int(input())
    A = list(map(int, input().split()))
    assert N == len(A)
    answer = 1
    if 0 in A:
        print(0)
        exit()
    for i in A:
        answer *= i
        if answer > limit:
            print("-1")
            exit()
    print(answer)


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

import sys
from heapq import heappush, heappop, heapify
N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
BC=[map(int, sys.stdin.readline().split()) for _ in range(M)]
heapify(A)

for b,c in BC:
    while A[0]<c and 0<b:
        a=heappop(A)
        heappush(A,c)
        b-=1
print sum(A)

### FIXED CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

B=[ map(int, sys.stdin.readline().split()) for _ in range(M)] 
B.sort(key=lambda x: x[1], reverse=True)

i=0

for b,c in B:
	for i in range(i,N):
		if A[i]<c and 0<b:
			A[i]=c
			b-=1
		if b==0:
			break
	i+=1

print sum(A)
### BUGGY CODE ###

def main():
  from fractions import Fraction
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  iterator = dd_ba.copy().items()
  for key,value in iterator:
    if dd_flag[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

  ans += zero_zero_count - 1
  print(ans%MOD) 

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

import heapq
from copy import deepcopy

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

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]


first_tmp = deepcopy(first)
second_tmp = deepcopy(second)
first_sum_tmp = first_sum
second_sum_tmp = second_sum
ans = -10 ** 15

# first側からk個を取り除き、second側からN - k個を取り除く
for k in range(N + 1):
    first = deepcopy(first_tmp)
    second = deepcopy(second_tmp)
    first_sum = first_sum_tmp
    second_sum = second_sum_tmp
    cnt = 0

    while cnt < k:
        heapq.heappush(first, a[N + cnt])
        first_sum += a[N + cnt]
        first_sum -= heapq.heappop(first)
        cnt += 1

    while cnt < N:
        heapq.heappush(second, -a[N + cnt])
        second_sum += a[N + cnt]
        second_sum -= -heapq.heappop(second)
        cnt += 1

    ans = max(ans, first_sum - second_sum)
    # print(first_sum, second_sum)

print(ans)


### FIXED CODE ###

import heapq
from sys import stdin

N = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]

# first, secondそれぞれ0 - Nまで探索
L_sum = [first_sum]
R_sum = [second_sum]

for i in range(N, 2 * N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    first_sum -= heapq.heappop(first)
    L_sum.append(first_sum)

    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]
    second_sum -= - heapq.heappop(second)
    R_sum.append(second_sum)

ans = -10 ** 15

R_sum = R_sum[::-1]

for i in range(N + 1):
    ans = max(ans, L_sum[i] - R_sum[i])

# print(L_sum, R_sum)
print(ans)
### BUGGY CODE ###

k = int(input())
def gcd(a, b, c):
    gcd1 = 1
    for i in range(2, c+1):
        if a%i == 0 and b%i == 0 and c%i == 0:
            gcd1 = i
    # print(gcd1)
    return gcd1

sum_gcd = 0
for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a == b and b == c:
                sum_gcd += gcd(a, b, c)
            elif a == b or b == c or c == a:
                sum_gcd += 3*gcd(a, b, c)
            else:
                sum_gcd += 6*gcd(a, b, c)
print(sum_gcd)


### FIXED CODE ###

k = int(input())
def gcd(a, b, c):
    gcd1 = 1
    if a%c == 0 and b%c == 0:
        gcd1 = c
    elif a%2 == 0 and b%2 == 0 and c%2 == 0:
        gcd1 = 2
        for i in range(4, c//2+1, 2):
            if a%i == 0 and b%i == 0 and c%i == 0:
                gcd1 = i
    else:
        for i in range(3, c//2+1, 2):
            if a%i == 0 and b%i == 0 and c%i == 0:
                gcd1 = i
    # print(gcd1)
    return gcd1

sum_gcd = 0
for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a == b and b == c:
                sum_gcd += gcd(a, b, c)
            elif a == b or b == c or c == a:
                sum_gcd += 3*gcd(a, b, c)
            else:
                sum_gcd += 6*gcd(a, b, c)
print(sum_gcd)
### BUGGY CODE ###

def lsum(x):
    return A[x[0]] + B[x[1]] + C[x[2]]

def nextlist():
    global lx
    idx = 0
    m = lsum(lx[0])
    for i in range(len(lx)):
        s = lsum(lx[i])
        if m < s:
            m = s
            idx = i
    p = lx.pop(idx)
    wa.append(lsum(p))
    if p[0] > 0:
        if not [p[0]-1, p[1], p[2]] in lx:
            lx.append([p[0]-1, p[1], p[2]])
    if p[1] > 0:
        if not [p[0], p[1]-1, p[2]] in lx:
            lx.append([p[0], p[1]-1, p[2]])
    if p[2] > 0:
        if not [p[0], p[1], p[2]-1] in lx:
            lx.append([p[0], p[1], p[2]-1])

l1 = list(map(int, input().split(" ")))

X,Y,Z,K = l1[0],l1[1],l1[2],l1[3]
A = sorted(list(map(int, input().split(" "))))
B = sorted(list(map(int, input().split(" "))))
C = sorted(list(map(int, input().split(" "))))

wa = []
lx = [[X-1,Y-1,Z-1]]

for i in range(K):
    nextlist()

for l in wa:
    print(l)


### FIXED CODE ###

def lsum(x):
    return A[x[0]] + B[x[1]] + C[x[2]]

def nextlist():
    global lx
    idx = 0
    m = lsum(lx[0])
    for i in range(len(lx)):
        s = lsum(lx[i])
        if m < s:
            m = s
            idx = i
    p = lx.pop(idx)
    wa.append(lsum(p))
    if p[0] > 0:
        if not [p[0]-1, p[1], p[2]] in lx:
            lx.append([p[0]-1, p[1], p[2]])
    if p[1] > 0:
        if not [p[0], p[1]-1, p[2]] in lx:
            lx.append([p[0], p[1]-1, p[2]])
    if p[2] > 0:
        if not [p[0], p[1], p[2]-1] in lx:
            lx.append([p[0], p[1], p[2]-1])

l1 = list(map(int, input().split(" ")))

X,Y,Z,K = l1[0],l1[1],l1[2],l1[3]
A = sorted(list(map(int, input().split(" "))))
B = sorted(list(map(int, input().split(" "))))
C = sorted(list(map(int, input().split(" "))))

wa = []
lx = [[X-1,Y-1,Z-1]]

for i in range(K):
    nextlist()

for l in wa:
    print(l)
### BUGGY CODE ###

#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]
def check(A,B):#A:prev,B:temp




    As = list(map(str,sorted(A,reverse=True)))
    p = int("".join(As)) if len(A) else 0

    B.sort(reverse=True)
    Bs = list(map(str,B))
    
    t = int("".join(Bs)) if len(B) else 0
    if t > p:
        return B
    else :
        return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check(bagS[b+c[a]],bagS[b]+[a])

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))



### FIXED CODE ###

#coding:utf-8
N,M  = map(int,input().split())
A = list(map(int,input().split()))
b = 0
c = [0,2,5,5,4,5,6,3,7,6]
bagS = [[] for i in range(N+1)]

def check2(A,B):
    p = 0
    t = 0
    # print(A)
    # print(B)
    if len(A) > len(B):
        return A
    elif len(A) < len(B):
        return B
    for a,b in zip(A,B):
        if  a- b > 0:
            return A
        elif a-b < 0:
            return B
    return A
    # for a in A:
    #     p = p*10+a
    # for b in B:
    #     t = t*10+b
    # if t > p:
    #     return B

    # else:
    #     return A

while b != N:

    for a in A:
        if b+ c[a] <= N:
  
            bagS[b+c[a]] = check2(bagS[b+c[a]],sorted((bagS[b]+[a]),reverse=True))

    for i in range(b+1,N+1):
        if bagS[i]:
            b = i
            break
print("".join(list(map(str,bagS[N]))))
### BUGGY CODE ###

from heapq import *

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        heappush(c[m - a], -b)
r=0
for i in range(m - 1, -1, -1):
    if c[i]:
        r -= heappop(c[i])
        if i:
            for x in c[i]:
                heappush(c[i - 1], x)  
print(r)


### FIXED CODE ###

from heapq import *

R = lambda: map(int, input().split())
n, m = R()
c = [[] for _ in range(m)]
for _ in range(n):
    a, b = R()
    if a <= m:
        heappush(c[m - a], -b)
r=0
for i in range(m - 1, -1, -1):
    if c[i]:
        r -= heappop(c[i])
        if i:
            f = len(c[i]) > len(c[i - 1])
            h, g = (c[i], c[i - 1]) if f else (c[i - 1], c[i])
            for x in g:
                heappush(h, x)
            if f:
                c[i - 1] = c[i]       
print(r)
### BUGGY CODE ###

import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_left(c, a)
    if j == 0:
        c.insert(0, a)
    else:
        c[j-1] = a
print(len(c))

### FIXED CODE ###

import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_right(c, -a)
    if j == len(c):
        c.append(-a)
    else:
        c[j] = -a
print(len(c))
### BUGGY CODE ###

L, R = [int(i) for i in input().split()]

c = set()

for i in range(L, R + 1):
  t = i % 2019
  if i in c:
    break
  c.add(i)


m = float('inf')
l = list(c)
for i in range(len(l)):
  for j in range(i + 1, len(l)):
    m = min(m, l[i] * l[j] % 2019)

print(m)


### FIXED CODE ###

L, R = [int(i) for i in input().split()]

c = set()

for i in range(L, R + 1):
  t = i % 2019
  if t in c:
    break
  c.add(t)


m = float('inf')
l = list(c)
for i in range(len(l)):
  for j in range(i + 1, len(l)):
    m = min(m, l[i] * l[j] % 2019)

print(m)
### BUGGY CODE ###

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

ans = 0
if N%2==1:
    for i in range(0,N,2):
        # print(i)
        if i==0:
            if A.count(i)!=1:
                # print('A',A)
                break
        elif A.count(i)!=2:
            # print('B',i)
            break
    else:
        ans = pow(2,(N-1)//2,10**9+7)
else:
    for i in range(1,N,2):
        if A.count(i)!=2:
            # print(i)
            break
    else:
        ans = pow(2,N//2,10**9+7)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
from fractions import gcd
from math import ceil
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations
ans = 0
d = Counter(A)
if N%2==1:
    for i in range(0,N,2):
        # print(i)
        if i==0:
            if d[i]!=1:
                # print('A',A)
                break
        elif d[i]!=2:
            # print('B',i)
            break
    else:
        ans = pow(2,(N-1)//2,10**9+7)
else:
    for i in range(1,N,2):
        if d[i]!=2:
            # print(i)
            break
    else:
        ans = pow(2,N//2,10**9+7)
print(ans)
### BUGGY CODE ###

k,s=map(int,input().split())
cnt=0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                cnt+=1
print(cnt)

### FIXED CODE ###

k,s=map(int,input().split())
c=0
#x>=y>=z
for i in range(k+1):
    for j in range(k+1):
        if 0<=s-i-j<=k:
          c+=1
print(c)
### BUGGY CODE ###

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

for i in range(M):
    temp = A.index((max(A)))
    tempM = M
    while temp == A.index((max(A))):
        if tempM > M:
            break
        A[A.index((max(A)))] //= 2
        M -= 1

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 * (-1), a))
heapq.heapify(a)
while m != 0:
    price = heapq.heappop(a) * (-1)
    price //= 2
    m -= 1
    heapq.heappush(a, (-1) * price)
print(sum(a) * (-1))
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def make_divisors(n):  # 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

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [False] * (A[-1]+1)
    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = True
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x]:
                flag = False
                break
        bl[a] = True
        if flag:
            answer += 1

    print(answer)

main()

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)
### BUGGY CODE ###

import sys

def main():
    N, M = map(int, input().split())
    a = [int(sys.stdin.readline().strip()) for _ in range(M)]

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i in a:
            dp[i] = 0
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

    atmp = -1
    if len(a) != 0:
        atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

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

n = int(input())
a = list(map(int,input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)