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

import sys
input = sys.stdin.buffer.readline


def solve(mid):
    """のぞいてもいいカードならTrueを返す"""
    dp = [False] * (k + 1)
    dp[0] = True
    if k <= a[mid]:
        return False
    for i, weight in enumerate(a):
        if i == mid:
            continue
        for w in range(k + 1)[::-1]:
            if w - weight < 0:
                continue
            dp[w] |= dp[w - weight]

    return True not in dp[k - a[mid]:k]
     

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

a.sort()
ok = 0
ng = n
if not solve(ok):
    print(0)
    exit()

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok + 1)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline


def solve(mid):
    """のぞいてもいいカードならTrueを返す"""
    dp = 1
    mask = (1 << k) - 1
    if k <= a[mid]:
        return False
    for i, weight in enumerate(a):
        if i == mid:
            continue
        dp |= dp << min(weight, k + 10)
        dp &= mask
    return dp >> (k - a[mid]) == 0
     

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

a.sort()
ok = 0
ng = n
if not solve(ok):
    print(0)
    exit()

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok + 1)
### BUGGY CODE ###

def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()


### FIXED CODE ###

def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()
### BUGGY CODE ###

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

for i in range(k):
  if a > 0:
    a-=1
  elif b > 0:
    b-=1

print(a,b)

### FIXED CODE ###

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

if a>=k:
  print(a-k, b)
else:
  print(0, max(0, b-(k-a)))
### BUGGY CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [A[k]-1 for k in range(N)]
now = 0
for k in range(1000):
    if (K>>k)&1 == 1:
        now = A[now]
    A = [A[A[l]] for l in range(N)]
print(now+1)


### FIXED CODE ###

N, K = map(int,input().split())
A = list(map(int,input().split()))
A = [A[k]-1 for k in range(N)]
now = 0
for k in range(70):
    if (K>>k)&1 == 1:
        now = A[now]
    A = [A[A[l]] for l in range(N)]
print(now+1)
### BUGGY CODE ###

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


ans = []
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if s[i] + s[j] + s[k] not in ans:
        ans.append(s[i] + s[j] + s[k])
      
print(len(ans))


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(10):
    a = s.find(str(i))
    if a == -1: continue
    for j in range(10):
        b = s.find(str(j), a + 1)
        if b == -1: continue
        for k in range(10):
            if s.find(str(k), b + 1) != -1:
                ans += 1
print(ans)
### BUGGY CODE ###

X, K, D = map(int, input().split())


count = 0
while count < K:
    if X >= 0:
        X -= D
        count += 1
    else:
        X += D
        count += 1
print(abs(X))

### FIXED CODE ###

X, K, D = map(int, input().split())

if abs(X) <= K * D:
    X2 = abs(X) % D
    K2 =  K - abs(X)//D
    if K2 % 2 == 0:
        print(abs(X2))
    else:
        print(min(abs(X2+D), abs(X2-D)))
else:
    print(abs(abs(X)-K*D))
### BUGGY CODE ###

S = input()
N = len(S)
L = [0 for _ in range(N)]

for i in range(N):
    a = i
    b = i
    if S[i] == 'R':
        b += 1
        while S[a] == S[b]:
            b += 1
        if (b-a) % 2 == 1:
            L[b-1] += 1
        else:
            L[b] += 1
    else:
        a -= 1
        while S[a] == S[b]:
            a -= 1
        if (b-a) % 2 == 1:
            L[a+1] += 1
        else:
            L[a] += 1
print(*L)

### FIXED CODE ###

S = input()
N = len(S)
L = [0 for _ in range(N)]
a = 0
b = 1
while a != N:
    if S[a] == 'R':
        while b != N and S[a] == S[b]:
            b += 1
        if b-a == 1:
            L[a] += 1
        elif (b-a) % 2 == 1:
            L[b] += (b-a) // 2
            L[b-1] += (b-a)//2+1
        else:
            L[b] += (b-a)//2
            L[b-1] += (b-a)//2
    else:
        while b != N and S[a] == S[b]:
            b += 1
        if b-a == 1:
            L[a] += 1
        elif (b-a) % 2 == 1:
            L[a-1] += (b-a) // 2
            L[a] += (b-a)//2+1
        else:
            L[a-1] += (b-a)//2
            L[a] += (b-a)//2
    a = b
    b = a+1
print(*L)
### BUGGY CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _i(): return int(sys.stdin.readline().strip())
def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
m = None
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)
    if m is None or m<t: m=t

# initialize
st = ab[0][0]
m = m * (h+w-2) + st + 1
dp = [[[False] * m for _ in range(w)] for _ in range(h)]
dp[0][0][st] = True
cnt = [ [0]*w for _ in range(h)]
cnt[0][0] = st+1
for ij in range(1,h+w-1):
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        x = ab[i][j]
        nxt = dp[i][j]
        #
        if i==0:
            ref= dp[i][j-1]
            oft= cnt[i][j-1]
        elif j==0:
            ref = dp[i-1][j]
            oft= cnt[i-1][j]
        else:
            oft = max(cnt[i][j-1],cnt[i-1][j])
            ref = list(map(lambda x: x[0]|x[1], zip(dp[i][j-1][:oft], dp[i-1][j][:oft])))
        #
        im = 0
        for idx,tf in enumerate(ref):
            if not tf: continue
            nxt[abs(idx-x)]= True
            ix = idx + x
            nxt[ix] = True
            if im<ix: im=ix
        #
        cnt[i][j] = im + 1
            
# stdout
ref=dp[h-1][w-1]
for k in range(m):
    if ref[k]:
        print(k)
        break


### FIXED CODE ###

#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/g.inp"; exit $?
exit 0
'''
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

# read input
h,w = _ia()
ab = []
for _ in range(h): ab.append(_ia())
for i in range(h):
    r = ab[i]
    for j,bj in enumerate(_ia()):
        r[j] = abs(r[j] - bj)
    t = max(r)

# initialize
dp = [[None for _ in range(w)] for _ in range(h)]
dp[0][0] = {ab[0][0]}
hw1 = h + w - 1
for ij in range(1,hw1):
    iend = ( hw1 - ij ) * 80
    for i in range(min(ij+1,h)):
        j = ij - i
        if j>=w: continue
        #
        ref = set()
        if i>0: ref|= dp[i-1][j]
        if j>0: ref|= dp[i][j-1]
        #
        x = ab[i][j]
        nxt = dp[i][j] = set()
        for idx in ref:
            ix = abs(idx-x)
            if ix<=iend: nxt.add(ix)
            ix = idx + x
            if ix<=iend: nxt.add(ix)
            
# stdout
print(min(dp[h-1][w-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)
    used = set()
    for i, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = True
            continue
        if a in used:
            continue
        used.add(a)
        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 ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

class BIT:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a

n,q=nii()
a=lnii()
Bit=BIT(n)
for i in range(n):
  Bit.add(i,a[i])
for i in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

class BIT:
  def __init__(self, n):
    self.bit = [0] * n

  def add(self, i, x):
    i += 1
    while i <= len(self.bit):
      self.bit[i-1] += x
      i += i & -i

  def sum_sub(self, i):
    a = 0
    i += 1
    while i:
      a += self.bit[i-1]
      i -= i & -i
    return a

  def sum(self, i, j):
    a = 0
    if j != 0:
      a += self.sum_sub(j-1)
    if i != 0:
      a -= self.sum_sub(i-1)
    return a

n,q=map(int,input().split())
a=list(map(int,input().split()))
Bit=BIT(n)
for i in range(n):
  Bit.add(i,a[i])
for i in range(q):
  t,a,b=map(int,input().split())
  if t==0:
    Bit.add(a,b)
  else:
    print(Bit.sum(a,b))
### BUGGY CODE ###

n,k = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
zeronum = min(n-1,k)
ans = 1
for zero in range(1,zeronum+1):
    count = comb(n,zero,mod)
    one = n-zero
    count = (count*comb(one+zero-1,zero,mod))%mod
    ans = (ans+count)%mod
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
mod = 10**9 + 7
zeronum = min(n-1,k)
comblist1 = []
comblist2 = []
ac = 1
for i in range(1,zeronum+1):
    ac = (ac*(n-i+1)*power_func(i,mod-2,mod))%mod
    comblist1.append(ac)
ac = 1
for i in range(1,zeronum+1):
    ac = (ac*(n-i)*power_func(i,mod-2,mod))%mod
    comblist2.append(ac)

ans = 1
for zero in range(1,zeronum+1):
    count = (comblist1[zero-1]*comblist2[zero-1])%mod
    ans = (ans+count)%mod
print(ans)
### BUGGY CODE ###

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


def key_search(dicti, item):
    for k, v in dicti.items():
        if v == item:
            return k


popu = {str(i): As[i] for i in range(n)}
jb = {str(i+1): int(key_search(popu, i+1)) + 1 for i in range(n)}

# print(popu)
# print(jb)

Ans = [jb[str(i+1)] for i in range(n)]
print(*Ans)








### FIXED CODE ###

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


def key_search(dicti, item):
    for k, v in dicti.items():
        if v == item:
            return k


# print(As)
sb = {str(i): As[i-1] for i in range(1, n+1)}
jb = {}
for i in range(1, n+1):
    # print(sb[str(i)])
    jb[sb[str(i)]] = i
srted = sorted(jb.items())

ans = [srted[i][1] for i in range(n)]
print(*ans)
### BUGGY CODE ###

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

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import math
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return (a // math.gcd(a, b)) * b

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)


### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)
### BUGGY CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split())) 
 
maxN=0
for i in range(N-K+1):
  sumN=(sum(P[i:i+K])+K)/2
  if sumN>=maxN:
    maxN=sumN
print(maxN)

### FIXED CODE ###

N,K = map(int, input().split())
P = list(map(int, input().split())) 
tmp=sum(P[:K])
maxN=tmp
for i in range(1,N-K+1):
  tmp=tmp-P[i-1]+P[i+K-1]
  if tmp>=maxN:
    maxN=tmp
print((maxN+K)/2)
### BUGGY CODE ###

H, W, A, B = [int(_) for _ in input().split()]
p = 10 ** 9 + 7


# 二分累乗法 で n^x % p を求める
# pow(n,x,p) で得られるので次からはそっちつかう
def power(n, x, p):
    a = n  # a^(2^0), a^(2^1), ...
    ans = 1
    while x > 0:
        if x & 1:
            ans = (ans * a) % p
        x = x >> 1
        a = (a ** 2) % p
    return ans


def solve():
    kaijo = [0] * (H + W + 1)
    kaijo[0] = kaijo[1] = 1
    for i in range(2, H + W + 1):
        kaijo[i] = (i * kaijo[i - 1]) % p
    gyaku = [0] * (H + W + 1)
    gyaku[0] = gyaku[1] = 1
    for i in range(2, H + W + 1):
        gyaku[i] = power(kaijo[i], p - 2, p)

    # for i in range(H + W + 1):
    #     assert (kaijo[i] * gyaku[i]) % p == 1, (kaijo[i], gyaku[i])

    def conb(_x, _y):
        return (kaijo[_x] * gyaku[_y] * gyaku[_x - _y]) % p

    # h = H - A - 1
    # h2 = H - (H - A)
    ans = 0
    for i in range(W - B):
        ans = (ans + conb(H - A - 1 + B + i, H - A - 1) * conb(A - 1 + W - 1 - B - i, A - 1)) % p
    # for i in range(B, W):
    #     tmp1 = kaijo[h + i] * gyaku[h + i] * gyaku[h + i - max(h, i)]
    #     j = W - i - 1
    #     tmp2 = kaijo[h2 + j] * gyaku[h2 + j] * gyaku[h2 + j - max(h2, j)]
    #     ans = (ans + tmp1 * tmp2) % p
    # print(ans)
    print(ans)


if __name__ == '__main__':
    solve()

### FIXED CODE ###

H, W, A, B = [int(_) for _ in input().split()]
p = 10 ** 9 + 7


# 二分累乗法 で n^x % p を求める
# pow(n,x,p) で得られるので次からはそっちつかう
def power(n, x, p):
    return pow(n,x,p)
    # a = n  # a^(2^0), a^(2^1), ...
    # ans = 1
    # while x > 0:
    #     if x & 1:
    #         ans = (ans * a) % p
    #     x = x >> 1
    #     a = (a ** 2) % p
    # return ans


def solve():
    kaijo = [0] * (H + W + 1)
    kaijo[0] = kaijo[1] = 1
    for i in range(2, H + W + 1):
        kaijo[i] = (i * kaijo[i - 1]) % p
    gyaku = [0] * (H + W + 1)
    gyaku[0] = gyaku[1] = 1
    for i in range(2, H + W + 1):
        gyaku[i] = power(kaijo[i], p - 2, p)

    # for i in range(H + W + 1):
    #     assert (kaijo[i] * gyaku[i]) % p == 1, (kaijo[i], gyaku[i])

    def conb(_x, _y):
        return (kaijo[_x] * gyaku[_y] * gyaku[_x - _y]) % p

    # h = H - A - 1
    # h2 = H - (H - A)
    ans = 0
    for i in range(W - B):
        ans = (ans + conb(H - A - 1 + B + i, H - A - 1) * conb(A - 1 + W - 1 - B - i, A - 1)) % p
    # for i in range(B, W):
    #     tmp1 = kaijo[h + i] * gyaku[h + i] * gyaku[h + i - max(h, i)]
    #     j = W - i - 1
    #     tmp2 = kaijo[h2 + j] * gyaku[h2 + j] * gyaku[h2 + j - max(h2, j)]
    #     ans = (ans + tmp1 * tmp2) % p
    # print(ans)
    print(ans)


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

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

n = int(raw_input())
dic = []
for i in range(n):
    com, s = map(str, raw_input().split())
    if com == "insert":
        dic.append(s)
    elif com == "find":
        if s in dic:
            print "yes"
        else:
            print "no"

### FIXED CODE ###

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

n = int(raw_input())
dic = set()
for i in range(n):
    com, s = map(str, raw_input().split())
    if com == "insert":
        dic.add(s)
    elif com == "find":
        if s in dic:
            print "yes"
        else:
            print "no"
### BUGGY CODE ###

#愚直にn^3
n = int(input())
l = list(map(int,input().split()))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            len = l[i]+l[j]+l[k]
            ma = max(l[i],max(l[j],l[k]))
            rest = len-ma
            if ma < rest:
                ans += 1
print(ans)

### FIXED CODE ###

#それゆけにぶたんまん
#python3.8.2のTLEの壁に阻まれました
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n):
    for j in range(i+1,n):
        #jより大きい整数kでl[k]<l[i]+l[j]を満たす最大のk
        le = j
        ri = n
        while ri-le>1:
            m = (ri+le)//2
            if l[m]<l[i]+l[j]:
                le = m
            else:
                ri = m
        ans += le-j

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

N=int(input())

A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())
#print(N,A,B,C,D,E)

def transport(situ):
    temp=[0]*6
    temp[0]+=situ[0]-min(A, situ[0])
    temp[1]+=min(A, situ[0])

    temp[1]+=situ[1]-min(B, situ[1])
    temp[2]+=min(B, situ[1])

    temp[2] += situ[2] - min(C, situ[2])
    temp[3] += min(C, situ[2])

    temp[3] += situ[3] - min(D, situ[3])
    temp[4] += min(D, situ[3])

    temp[4] += situ[4] - min(E, situ[4])
    temp[5] += min(E, situ[4])

    temp[5]+=situ[5]

    return temp

popu=[N, 0, 0, 0, 0, 0]
time=0
while popu!=[0, 0, 0, 0, 0, N]:
    popu=transport(popu)
    time+=1

print(time)


### FIXED CODE ###

import math

N=int(input())
A=int(input())
B=int(input())
C=int(input())
D=int(input())
E=int(input())

spent=[A,B,C,D,E]
limit=min(spent)
limit_index=spent.index(limit)
print(math.ceil(N/limit)-1+5)
### BUGGY CODE ###

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


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]

for i in a:
    b[i - 1] += 1

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

import fractions
from functools import reduce

def lcm_base(x, y):
  return (x*y) // fractions.gcd(x,y)
def lcm_list(numbers):
  return reduce(lcm_base,numbers,1)

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

if N==1:
  print(1)
else:
  alist.sort()
  lcm_alist=lcm_list(alist)
  
  answer=0
  last_a=-1
  last_b=-1
  for a in alist:
    b=last_b
    if a!=last_a:
      b=lcm_alist//a
      last_a=a
      last_b=b

    answer=(answer+b)%(10**9+7)
    
  #print(blist)
  print(answer)

### FIXED CODE ###

import fractions
import sys
from functools import reduce

def lcm_base(x, y):
  return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

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

if N==1:
  print(1)
else:
  lcm_alist=lcm_list(alist)
  #print(lcm_alist)
  
  allsum=0
  for i in range(N):
    allsum+=lcm_alist//alist[i]
    
  #print(blist)
  print(allsum%(10**9+7))
### BUGGY CODE ###

#D
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
heapq.heapify(a)

for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        p = heapq.heappop(a)
        if c > p:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,p)
            break
            
print(sum(a))

### FIXED CODE ###

#D
import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
bc = []
for i in range(m):
    b,c = map(int,input().split())
    bc.append((b,c))
bc.sort(key=lambda x:-x[1])
heapq.heapify(a)
for i in range(m):
    b,c = bc[i][0],bc[i][1]
    for j in range(b):
        p = heapq.heappop(a)
        if c > p:
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,p)
            break
            
            
print(sum(a))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N,Q=map(int,input().split())
ab=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

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


count=[-1]*N
c=0
def dfs(p):
  global c
  c+=P[p-1]
  count[p-1]=c
  for i in ab[p-1]:
    if count[i-1]==-1:
      dfs(i)
  c-=P[p-1]

dfs(1)
print(" ".join(map(str,count)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=lambda :sys.stdin.readline()
N,Q=map(int,input().split())
ab=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

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

def dfs(p,par):
  for i in ab[p-1]:
    if i!=par:
      P[i-1]+=P[p-1]
      dfs(i,p)

dfs(1,-12345)
print(" ".join(map(str,P)))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
def xor(b,c):
    if b==c:
        return(b)
    k=0
    s=0
    while b>=1 or c>=1:
        if b%2!=c%2:
            k+=2**s
        b//=2
        c//=2
        s+=1
    return(k)
z=0
for i in range(n):
    x=a[i]
    y=a[i]
    for j in range(i,n):
        q=a[j]
        if i!=j:
            x=xor(x,q)
            y+=q
            if x==y:
                z+=1
        else:
            z+=1
print(z)

### FIXED CODE ###

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

total = alst[0]
xor = alst[0]
ans = 0
l = 0
r = 0
while 1:
    if xor == total:
        ans += r - l + 1
        r += 1
        if r == n:
            break
        total += alst[r]
        xor ^= alst[r]
    else:
        total -= alst[l]
        xor ^= alst[l]
        l += 1
print(ans)