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

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

dp = [-1] * (W + 1)
dp[0] = 0

for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        if dp[i] == -1: continue
        dp[i + w] = max(dp[i + w], dp[i] + v)

print(max(dp))


### FIXED CODE ###

def main():
    N, W =  list(map(int, input().split()))

    dp = [-1] * (W + 1)
    dp[0] = 0

    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] != -1 and dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v

    print(max(dp))

main()
### BUGGY CODE ###

N = int(input())
list_S = [input() for i in range(N) ]
list_S.sort()
list_a = []
a = 0
while a < N :
    list_a.append(list_S.count(list_S[a]))
    a += list_S.count(list_S[a])
newlist_a = sorted(list_a,reverse=True)
n = newlist_a.count(newlist_a[0])

ans = ""
if n == 1:
    t = list_a.index(newlist_a[0])
    m = 0
    for i in range(t):
        m += list_a[i]
    ans +=list_S[m+t]
else:
    if newlist_a[0]==1:
        for i in range(len(list_S)):
            ans += list_S[i]
            ans += "\n"
    else:            
        list_A = []
        for i in range(len(list_a)):
            list_A.append(list_a[i])
        list_t = []
        list_t.append(list_A.index(newlist_a[0]))
        for i in range(n-1):
            list_A.remove(newlist_a[i])
            m = 0
            for j in range(list_A.index(newlist_a[i])+i+1):
                m += list_a[j]
            list_t.append(m)
        for i in range(len(list_t)):
            ans += list_S[list_t[i]]
            ans += "\n"
print(ans)


### FIXED CODE ###

import collections

N = int(input())
S = [input() for i in range(N)]
c =collections.Counter(S)
C = c.most_common()
list_C = []
for i in range(len(c)):
    list_C.append(C[i][1])
m = 1
for i in range(len(list_C)-1):
    if list_C[i]==list_C[i+1]:
        m += 1
    else:
        break
ans= []
for i in range(m):
    ans.append(C[i][0])
ans = sorted(ans)
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

def knapsack_DP(N, W, weight, value):
    dp = [0 for _ in range(W + 1)] 

    for i in range(N):
        dp_tmp = [] 
        for w in range(W + 1):
            if (w >= weight[i]): 
                dp_next = max(dp[w-weight[i]] + value[i], dp[w]) 
            else:
                dp_next = dp[w] 
            dp_tmp.append(dp_next)
        dp = dp_tmp 
    return dp[-1]

if __name__=="__main__":
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    wv=((weight[i],value[i]) for i in range(N))
    wv=sorted(wv)
    weight=[wv[i][0] for i in range(N)]
    value=[wv[i][1] for i in range(N)]
    ans=0
    for i in range(1,N):
        if i==0:
          wtmp=weight[1:]
          vtmp=value[1:]
        elif i==N-1:
          wtmp=weight[:N-1]
          vtmp=value[:N-1]
        else:
          wtmp=weight[:i]+weight[i+1:]
          vtmp=value[:i]+value[i+1:]
        ans=max(knapsack_DP(N-1, W-1, wtmp, vtmp)+value[i], ans)
    print(ans)

### FIXED CODE ###

def knapsack_DP(N, W, weight, value):
    import numpy as np
    dishes = [(weight[i], value[i]) for i in range(N)]
    dishes = sorted(dishes, key=lambda x: x[0])
    dp = np.zeros(W, dtype=int)
    ans=0
    for w, v in dishes:
        ans=max(dp[-1]+v, ans)
        np.maximum(dp[:-w] + v, dp[w:], out=dp[w:]) 
    return ans

if __name__=="__main__":
    N, W = map(int, input().split())
    weight = []
    value = []
    for i in range(N):
        w, v= map(int, input().split())
        weight.append(w)
        value.append(v)
    print(knapsack_DP(N, W, weight, value))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n

if (z == x):
  u = n - 1
  d = n - 1
elif (z == o):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
  ans[i] = solve(i, 0)
for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  if(x[i] == '0'):
    print(solve2(int(_x, 2), u))
  else:
    print(solve2(int(_x, 2), d))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
### BUGGY CODE ###

s = input()
n = len(s)
target = 2019
res = 0
for i in range(n):
    j = i + 4
    while j < n:
        if int(s[i:j+1]) % target == 0:
            res += 1
        j += 1
print(res)

### FIXED CODE ###

from collections import defaultdict
s = input()
n = len(s)
target = 2019
res = 0
dic = defaultdict(int)
dic[0] = 1
s = s[::-1]
num, d = 0, 1
for char in s:
    num += int(char) * d
    num %= target
    d *= 10
    d %= target
    dic[num] += 1
for i in dic.values():
    res += i * (i -1) //2
print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
arr = [0] + list(map(int, input().split())) + [0] * 1000

INF = 1 << 60
dp = [INF] * (n + 1000)

dp[1] = 0

for i in range(1, n):
    for k in range(1, k + 1):
        dp[i + k] = min(dp[i + k], dp[i] + abs(arr[i + k] - arr[i]))

print(dp[n])

### FIXED CODE ###

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

# dp初期化
dp = [float("inf")] * n
dp[0] = 0

for i in range(1, n):
    dp[i] = min(dp[j] + abs(arr[i] - arr[j]) for j in range(max(i - k, 0), i))

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

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
money = [[] for _ in range(10**5)]
dp = [0] * m

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

max1 = []
for i in range(m):
    max1 += money[i]
    max1.sort(reverse = True)
    if max1:
        dp[i] = max1.pop(0)
    if i >= 1:
        dp[i] += dp[i-1]

print(dp[-1])


### FIXED CODE ###

import sys
import heapq
imput = sys.stdin.readline

def main():
    n,m = map(int,input().split())
    money = [[] for _ in range(10**5)]
    dp = [0] * m
    hq = []
    heapq.heapify(hq)

    for _ in range(n):
        a,b = map(int,input().split())
        money[a-1] += [b]

    for i in range(m):
        for j in money[i]:
            heapq.heappush(hq,-j)
        if hq:
            dp[i] += -heapq.heappop(hq)
        if i >= 1:
            dp[i] += dp[i-1]
    print(dp[-1])

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

MAX_NUM = 10 ** 18

def main():
    import math
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    for i in range(N):
        ans = ans * A[i]
        
        if(ans > MAX_NUM):
            ans = -1
            if(A[i] == 0):
                ans = 0
                break

    print(ans)



main()

### FIXED CODE ###

MAX_NUM = 10 ** 18

def main():
    import math
    N = int(input())
    A = list(map(int, input().split()))
    A_set = set(A)
    log_sum = 0
    if(0 in A_set):
        print("0")
        return
    
    A_log = [0] * N
    ans = 1
    for i in range(N):
        log_sum += math.log10(A[i])
        if(log_sum > 18):
            ans = -1
            break
        else:
            ans = ans * A[i]
            if(ans > MAX_NUM):
                ans = -1
                break
    print(ans)



main()
### BUGGY CODE ###

import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===


def main():
    n = ni()
    a = na()
    bit = [[0] * 20 for _ in range(n)]
    bitidx = [[] * 20 for _ in range(20)]

    for i, ai in enumerate(a):
        cnt = 0
        while ai > 0:
            if ai & 1:
                bit[i][cnt] = 1
                bitidx[cnt].append(i)
            cnt += 1
            ai >>= 1

    ans = n

    for i in range(n):
        min_idx = n
        for j in range(20):
            # jbit目でiの次に1になるidxを探す　ない場合はlen(bitidx[j])が返ってくる
            tmp = bisect.bisect_left(bitidx[j], i + 1)
            if bit[i][j]:
                # 1のときは次の1を探す
                if tmp < len(bitidx[j]):
                    tmp = bitidx[j][tmp]
                else:
                    tmp = n
            else:
                # 0のときは2つ目の1を探す
                tmp += 1
                if tmp < len(bitidx[j]):
                    tmp = bitidx[j][tmp]
                else:
                    tmp = n
            min_idx = min(min_idx, tmp)
        ans += min_idx - i - 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
import collections
import bisect
import copy
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===


def main():
    n = ni()
    a = na()
    bit = [[0] * 20 for _ in range(n)]
    bitidx = [[] * 20 for _ in range(20)]

    for i, ai in enumerate(a):
        cnt = 0
        while ai > 0:
            if ai & 1:
                bit[i][cnt] = 1
                bitidx[cnt].append(i)
            cnt += 1
            ai >>= 1

    ans = n

    for i in range(n):
        min_idx = n
        for j in range(20):
            # jbit目でiの次に1になるidxを探す　ない場合はlen(bitidx[j])が返ってくる
            tmp = bisect.bisect_left(bitidx[j], i + 1)
            if bit[i][j]:
                # 1のときは次の1を探す
                if tmp < len(bitidx[j]):
                    tmp = bitidx[j][tmp]
                else:
                    tmp = n
            else:
                # 0のときは2つ目の1を探す
                tmp += 1
                if tmp < len(bitidx[j]):
                    tmp = bitidx[j][tmp]
                else:
                    tmp = n
            min_idx = min(min_idx, tmp)
        ans += min_idx - i - 1

    print(ans)


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

n,q=map(int,input().split())
s=input()
a=[s[i:i+2]=="AC" for i in range(n-1)]
for i in range(q):
  l,r=map(int,input().split())
  print(sum([x for x in a[l-1:r-1]]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0 for _ in range(n)]
for i in range(n-1):
  a[i+1]=a[i]+(1 if s[i:i+2]=="AC" else 0)
for i in range(q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])
### BUGGY CODE ###

N = int(input())

result = {}

for i in range(N):
    s = input()
    if s in result.keys():
        result[s] += 1
    else:
        result[s] = 0
result_max = sorted([i for i in result.keys() if result[i] == max(result.values())])

for r in result_max:
    print(r)

### FIXED CODE ###

import collections


N = int(input())

S = [input() for i in range(N)]

count = collections.Counter(S)


mx = max(count.values())

result = [key for key, val in count.items() if val == mx]
print("\n".join(sorted(result)))
### BUGGY CODE ###

N = int(input())
A = input().split()

for i in range(1,N+1):
    print(A.count(str(i)))


### FIXED CODE ###

N = int(input())
A = input().split()

import collections
c = collections.Counter(A)

for i in range(1,N+1):
    print(c[str(i)])
### BUGGY CODE ###

N, M, K = map(int, input().split())
ans = []
child = {i:[] for i in range(1, N+1)}
isBlocked = {i:[] for i in range(1, N+1)}

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].append(d)
    isBlocked[d].append(c)
    
for i in range(1, N+1):
    x = [i]
    ch = set(child[i])
    while ch:
        c = ch.pop()
        ch = (ch | set(child[c])) - set(x)
        x.append(c)
    ans.append(len(set(x) - set(isBlocked[i])) - 1 - len(child[i]))
    
print(*ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])
### BUGGY CODE ###

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

ans = [0 for i in range(n)]
c = 0
c1 = n
for i in range(n) :
  f = 0
  f1 = 0
  c += 1
  for j in range(n) :
    if a[j] == c :
      ans[c-1] = j + 1
      f = 1
    if a[j] == c1 :
      ans[c1-1] = j + 1
      f1 = 1
    if f == 1 and f1 == 1 :
      break
print(*ans)

### FIXED CODE ###

import numpy as np

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

ans = np.argsort(a)
ans += 1

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

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
print(ans%mod)


### FIXED CODE ###

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
    po%=mod
print(ans%mod)
### BUGGY CODE ###

import numpy as np
N, M, Q = list(map(int, input().split()))
p_q = []
MAP = np.zeros([500, 500], dtype = int)

for _ in range(M):
    L, R = list(map(int, input().split()))
    MAP[L - 1][R - 1] += 1
for _ in range(Q):
    p, q = list(map(int, input().split()))
    p_q.append((p, q))

for i in p_q:
    print(np.sum(MAP[i[0] - 1:i[1], i[0] - 1:i[1]]))


### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())
X = np.zeros((N, N), dtype=int)
ends = np.zeros((M, 2), dtype=int)
queries = np.zeros((Q, 2), dtype=int)
for i in range(M):
    ends[i] = [int(item) for item in input().split()]
for i in range(Q):
    queries[i] = [int(item) for item in input().split()]
np.add.at(X, [ends[:,0] - 1, ends[:, 1] - 1], 1)
B = np.cumsum(X[::-1,:], axis = 0)[::-1,:]
C = np.cumsum(B, axis = 1)
for item in queries:
    print(C[item[0] - 1, item[1] - 1])
### BUGGY CODE ###

N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

ans = DP[M-1][(1 << N)-1]
if ans == inf:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

ans = DP[M-1][(1 << N)-1]
if ans == inf:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for j in range(n):
            if table[tmp][j] and dist[j]==-1:
                table[tmp][j] = table[j][tmp] = 0
                dist[j] = tmp+1
                next.append(j)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[0]*n for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1][b-1] = table[b-1][a-1] = 1
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**6)
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def BFS(n,m,table,dist):
    next = deque([0])
    while next:
        tmp = next.popleft()
        for rep in table[tmp]:
            if dist[rep]==-1:
                dist[rep] = tmp+1
                next.append(rep)
    return not -1 in dist

def main():
    n,m = IL()
    table = [[] for _ in range(n)]
    for _ in range(m):
        a,b = IL()
        table[a-1].append(b-1)
        table[b-1].append(a-1)
    dist = [-1]*n
    dist[0] = 0
    if BFS(n,m,table,dist):
        print('Yes')
        for i in range(1,len(dist)):
            print(dist[i])
    else:  print('No')
    return

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

x,k,d=map(int,input().split())
mini=0
l1=x-d
l2=x+d
for i in range(k):
 if abs(l1)<abs(l2):
  mini=abs(l1)
  l1=mini-d
  l2=mini+d
 else:
  mini=abs(l2)
  l1=mini-d
  l2=mini+d
print(mini)

### FIXED CODE ###

x,k,d=map(int,input().split())
mini=0
if abs(x)>=k*d:
 mini=abs(x)-k*d
 print(mini)
else:
 q=abs(x)//d
 s=abs(x)%d
 if (k-q)%2==0:
  print(s)
 else:
  print(abs(s-d))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)
LCM = A[0]
for i in range(1, N):
	GCD = gcd(LCM, A[i])
	LCM *= A[i]
	LCM //= GCD

ans = 0
for i in range(N):
	ans += LCM//A[i]
	ans %= mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)
LCM = A[0]
for i in range(1, N):
	GCD = gcd(LCM, A[i])
	LCM *= A[i]
	LCM //= GCD
LCM %= mod
ans = 0
for i in range(N):
	t = LCM * pow(A[i], mod-2, mod)
	ans += t
	ans %= mod

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

N=int(input())
alist=list(map(int,input().split()))
#print(alist)

dic_a={}
for a in alist:
  if not a in dic_a:
    dic_a[a]=1
  else:
    dic_a[a]+=1
    
dic2_a={}
for key in dic_a:
  if dic_a[key]>=2:
    dic2_a[key]=dic_a[key]
    
#print(dic2_a)
dic_answer={}
for a in alist:
  if a in dic_answer:
    print(dic_answer[a])
    continue
  
  dic2_a_copy=dic2_a.copy()
  if a in dic2_a_copy:
    dic2_a_copy[a]-=1
  
  #print(dic_a_copy)
  answer=0
  for val in dic2_a_copy.values():
    answer+=val*(val-1)//2
    
  print(answer)
  dic_answer[a]=answer

### FIXED CODE ###

N=int(input())
alist=list(map(int,input().split()))
#print(alist)

dic_a={}
for a in alist:
  if not a in dic_a:
    dic_a[a]=1
  else:
    dic_a[a]+=1
    
all_pair=0
for val in dic_a.values():
  all_pair+=val*(val-1)//2

#print(dic_a,all_pair)
dic_answer={}
for a in alist:
  if a in dic_answer:
    print(dic_answer[a])
    continue
  
  now=dic_a[a]
  kill=now*(now-1)//2-(now-1)*(now-2)//2
  answer=all_pair-kill
  
  print(answer)
  dic_answer[a]=answer
### BUGGY CODE ###

import bisect
n = int(input())
a = list(map(int,input().split()))

s = [0]*(n+1)

for i,e in enumerate(a):
    s[i+1] = s[i] + e

ans = 0
for i in range(1,n+1):
    sl = sorted(s[:i])
    l = bisect.bisect_left(sl,s[i])
    r = bisect.bisect_right(sl,s[i])

    ans += r-l

print(ans)


### FIXED CODE ###

import bisect
import math
n = int(input())
a = list(map(int,input().split()))

s = [0]*(n+1)

for i,e in enumerate(a):
    s[i+1] = s[i] + e

def comb(n,m):
    return math.factorial(n)//math.factorial(m)//math.factorial(n-m)

ans = 0
s = sorted(s)

l = 0
r = 0
#print(s)
while l < n+1:
    while r < n+1  and s[l] == s[r]:
        #print(r,s[r])
        r += 1

    if r-l >= 2:
        ans += comb(r-l,2)
    l = r

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

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

HP = sum(H)
count = 0
Z = 0
if K >= len(H):
    print(0)

else:
    for k in range(K):
        Z += sorted(H, reverse=True)[k]
    hp = HP - Z
    while(hp > 0):
        hp = hp - 1
        count += 1
    print(count)

### FIXED CODE ###

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

HP = sum(H)
ld = sorted(H , reverse=True)
if K >= len(H):
    print(0)

else:
    Z = sum(ld[:K])
    hp = HP - Z
    print(hp)
### BUGGY CODE ###

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


### FIXED CODE ###

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

N = int(input())
temp = []
for i in range(N):
    x = input()
    if not x in temp:
        temp.append(x)
print(len(temp))

### FIXED CODE ###


N = int(input())
s = set()
for i in range(N):
    x = input()
    s.add(x)
print(len(s))
### BUGGY CODE ###

S = input()
ans = 0

for i in range(len(S) - 3):
    for j in range(i + 4, len(S) + 1):
        if int(S[i:j]) % 2019 == 0:
            ans += 1

print(ans)

### FIXED CODE ###

S = input()
mod = 2019
count = [0] * 2019
count[0] = 1
tmp = 0
d = 1

for s in S[::-1]:
    tmp += int(s) * d
    count[tmp % mod] += 1
    d *= 10
    d %= mod

ans = 0

for c in count:
    ans += c * (c - 1) // 2
        
print(ans)
### BUGGY CODE ###

N = int(input())
l = list(map(int, input().split()))
l.append(0)
for i in range(1, len(l)+1):
    print(l.count(i))

### FIXED CODE ###

from collections import Counter
N = int(input())
l = list(map(int, input().split()))
counter = Counter(l)
for i in range(1, N+1):
    if i in counter.keys():
        print(counter[i])
    else:
        print(0)