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

N=int(input())
a=[int(i) for i in input().split()]
for j in range(N):
    print(a[j:].count(j+1))


### FIXED CODE ###

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

d = {}

for i in range(N - 1):
    if A[i] in d:
        d[A[i]].append(i + 2)
    else:
        d[A[i]] = [i + 2]

for i in range(1, N + 1):
    if i in d:
        print(len(d[i]))
    else:
        print(0)
### BUGGY CODE ###

N = int(input())

def factorization(n):
    if (n == 1 ):
        return [1]
    arr = []
    temp = n

    
    for i in range(2, int(-(-n**0.5//1))+1) :
        if ( temp % i == 0):
            cnt = 0
            while (temp % i == 0):
                cnt +=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return [arr[1]+1 for arr in arr ]

#print(factorization(N))

sum_ans = 0
def cal(list):
    ans = 1
    for i in list:
        ans *= i

    return ans


for i in range(1,N+1):
    #print(factorization(i),i)
    sum_ans += i * cal(factorization(i))
    #lenが掛け算

print(sum_ans)



### FIXED CODE ###


"""
def factorization(n):
    if (n == 1 ):
        return [1]
    arr = []
    temp = n

    
    for i in range(2, int(-(-n**0.5//1))+1) :
        if ( temp % i == 0):
            cnt = 0
            while (temp % i == 0):
                cnt +=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return [arr[1]+1 for arr in arr ]

#print(factorization(N))

sum_ans = 0
def cal(list):
    ans = 1
    for i in list:
        ans *= i

    return ans


for i in range(1,N+1):
    #print(factorization(i),i)
    sum_ans += i * cal(factorization(i))
    #lenが掛け算

print(sum_ans)
"""
n=int(input())
ans=0
for i in range(1,n+1):
    d=n//i
    ans+=i*d*(d+1)//2
print(ans)
### BUGGY CODE ###

N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x

max_n=max(x)

#dp=[[[0]*(max_n*N+1) for k in range(N+1)] for j in range(N+1)]
dp=[[[0]*3000 for k in range(51)] for j in range(51)]
#print dp


for j in range(N+1):
	for k in range(N+1):
		for s in range(max_n*N+1):
			if j==k==s==0:
				dp[j][k][s]=1
			elif j>=1 and s<x[j]:
				dp[j][k][s]=dp[j-1][k][s]
			elif j>=1 and k>=1 and s>=x[j]:
				dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-x[j]]
			else:
				dp[j][k][s]=0
#print dp


ans=0
for k in range(1,N+1):
	ans+=dp[N][k][k*A]

print ans
	
			
		

### FIXED CODE ###

N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x
y=map(lambda i:i-A, x)
#print y

max_x=max(max(x),A)
#print max_x

dp=[[0]*(2*N*max_x+1) for i in range(N+1)]

for j in range(N+1):
	for t in range(2*N*max_x):
		if j==0 and t==N*max_x:
			dp[j][t]=1
		elif j>=1 and (t-y[j]<0 or t-y[j]>2*N*max_x):
			dp[j][t]=dp[j-1][t]
		elif j>=1 and t-y[j]>=0 and 2*N*max_x>=t-y[j]: 
			dp[j][t]=dp[j-1][t]+dp[j-1][t-y[j]]
		else:
			dp[j][t]=0

print dp[N][N*max_x]-1
### BUGGY CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

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

if N == 1:
    print(M)
    exit()

x = M//N

while 1:
    if M % x == 0:
        ans = x
        break
    x -= 1
    
print(ans)

### FIXED CODE ###

# D - Partition
# Mの約数で、しかもN倍してもMを超えないもののうち、最大のものを探す

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

if N == 1:
    print(M)
    exit()

x = M//N

while 1:
    if M % x == 0:
        ans = x
        break
    x -= 1
    
print(ans)
### BUGGY CODE ###

H = int(input())
ans = 0
while H > 0:
    if H == 1:
        ans += 1
    else:
        e = H // 2
        ans += e
        H -= 1
print(ans)


### FIXED CODE ###

H = int(input())
c = 0
ans = 0
while H > 1:
    H = H // 2
    c += 1
for i in range(c + 1):
    ans += 2 ** i
print(ans)
### BUGGY CODE ###

from collections import deque
H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(input()) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    list=[]
    for i in range(len(q)):
        a=q.popleft()
        #print(a)
        list.append(a)
    #print(list)
    for i in list:
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)

### FIXED CODE ###

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

H ,W = map(int, input().split())#↓H行数 →W列数
List = [list(str(input())) for i in range(H)]
#H=3
#W=3
#List=[['.', '.', '.'], ['.', '#', '.'], ['.', '.', '.']]
cheak=[['0' for i in range(W)] for j in range(H)]

q = deque([])

for h in range(H):
    for w in range(W):
        if List[h][w]=='#':
            cheak[h][w]='1'
            q.append([h,w])
#print(List)
#print(cheak)
move=[[1,0],[-1,0],[0,1],[0,-1]]
num=-1
#print(q)
while q:
    for rt in range(len(q)):
        i=q.popleft()
        for u in move:
            if 0<=i[0]+u[0]<=H-1 and 0<=i[1]+u[1]<=W-1 and cheak[i[0]+u[0]][i[1]+u[1]]=='0':
                q.append([i[0]+u[0],i[1]+u[1]])
                cheak[i[0]+u[0]][i[1]+u[1]]='1'
    #print(cheak)
    num+=1
print(num)
### BUGGY CODE ###

s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
keta=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*keta + mod) % 13
            dp[i+1][nmod] += dp[i][mod]
    keta*=10
    keta%=13

print(dp[-1][5]%MOD)

### FIXED CODE ###

s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
keta=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*keta + mod) % 13
            dp[i+1][nmod] += dp[i][mod]
    keta*=10
    keta%=13

print(dp[-1][5]%MOD)
### BUGGY CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
#print(L)

#b-a < c < a+b
#a<=b<=c
ans=0
L_a=L[:N-2]
for i,a in enumerate(L_a):
    L_b=L[i+1:N-1]
    for j,b in enumerate(L_b,start=i+1):
        x=bisect.bisect(L[j+1:],a+b)
        ans+=x
        if L[j+x]==a+b:
            ans-=1
        #print(i,a,j,b,x,N-j-1,L[j+1:])
print(ans)

### FIXED CODE ###

import bisect
import collections
N=int(input())
L=list(map(int,input().split()))
L.sort()
c = collections.Counter(L)
#print(L)
 
#b-a < c < a+b

#a<=b<=c
ans=0
L_a=L[:N-2]
for i,a in enumerate(L_a):
    L_b=L[i+1:N-1]
    for j,b in enumerate(L_b,start=i+1):
        x=bisect.bisect(L[j+1:],a+b)
        ans+=x
        if a+b==L[j+x]:
            #print(a,b,L[j+x])
            ans-=c[a+b]
        #print(i,a,j,b,x,N-j-1,L[j+1:])
print(ans)
### BUGGY CODE ###

import sys, copy

num = int(sys.stdin.readline())

if num==1:
    print(0)
    quit()
    
mm = list(map(int, sys.stdin.readline().split()))
for _ in range(num-1):
    mm.append(int(sys.stdin.readline().split()[1]))

used = [False] * num
seq = [0] * (num-2)
minv = 0
j=mm[1]
for i in mm[2:]:
    minv += i*j
    j=i
minv *= mm[0]    

def sequence(n, k, m, t):
    global minv, used, seq
    if k==m:
        t += mm[0]*mm[used[1:].index(False)+1]*mm[num]
        if minv>t:    minv = t
    else:
        for i in range(1,n+1):
            if used[i]: continue
            seq[m] = i
            used[i]=True

            l=i-1
            while l>0 and used[l]:     l-=1
            u=i+1
            while u<num and used[u]:   u+=1
            v = mm[l]*mm[i]*mm[u]
            if minv>t+v: sequence(n, k, m+1, t+v)
            used[i]=False

sequence(num-1, num-2, 0, 0)

print(minv)


### FIXED CODE ###

import sys

n = int(sys.stdin.readline())

m = list(map(int, sys.stdin.readline().split()))
for _ in range(n-1):
    _, a = sys.stdin.readline().split()
    m.append(int(a))

c = [[-1 for _ in range(n)] for _ in range(n)]

def val(a, b):
    if a==b: return 0
    if c[a][b]>0: return c[a][b]
    c[a][b]=val(a+1,b)+m[a-1]*m[a]*m[b]
    for k in range(a+1, b):
        v=val(a,k)+val(k+1,b)+m[a-1]*m[k]*m[b]
        if c[a][b]>v: c[a][b]=v
    return c[a][b]

print(val(0, n-1))
### BUGGY CODE ###

# 部分点解
s = input()
k = int(input())
n = len(s)
subs = []
for i in range(n):
    for j in range(n-i):
        subs.append(s[i:i+j+1])
print(sorted(set(subs))[k-1])

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
subs = []
for i in range(n):
    for j in range(min(5, n-i)):
        subs.append(s[i:i+j+1])
print(sorted(set(subs))[k-1])
### BUGGY CODE ###

### 動的計画法のテーブルを用意
# dp(n) は頂点nを始点として時の最大有効パスの長さ

def get_inputs():
    N, M = map(int, input().split())

    # グラフgを初期化
    g = [[] for _ in range(N)]

    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)

    return N, M, g


def getlp(x, depth):
    global dp, g

    if depth >= MAX_DEPTH:
        return -1
    elif dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        mxp = 0
        for y in g[x]:
            yp = getlp(y, depth + 1)
            if yp == -1:
                return -1
            elif yp > mxp:
                mxp = yp
        dp[x] = mxp + 1
        return dp[x]


N, M, g = get_inputs()
MAX_DEPTH = 500

dp = [-1] * N
nodes = list(range(N))
ans = 0

while len(nodes) > 0:
    tmp_nodes = []
    for x in range(N):
        if dp[x] == -1:
            t = getlp(x, 0)
            if t == -1:
                tmp_nodes.append(x)
            else:
                ans = max(ans, t)
        else:
            ans = max(ans, dp[x])

    nodes = list(tmp_nodes)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

def get_inputs():
    N, M = map(int, input().split())
    
    # グラフgを初期化
    g = [[] for _ in range(N)]
    
    # 辺情報を読み込みgに追加
    for _ in range(M):
        x, y = map(lambda c: int(c) - 1, input().split())
        g[x].append(y)
    
    return N, M, g


def getlp(x):
    global dp, g
    
    if dp[x] != -1:
        return dp[x]
    elif len(g[x]) == 0:
        dp[x] = 0
        return dp[x]
    else:
        dp[x] = max([getlp(y) for y in g[x]]) + 1
        return dp[x]


N, M, g = get_inputs()

dp = [-1] * N
ans = 0
for x in range(N):
    ans = max(ans, getlp(x))

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

n,m,k=map(int,input().split())
l=list(map(int,input().split()))
ll=list(map(int,input().split()))

l_l=[0]
for i in range(1,m+1):
  l_l.append(l_l[i-1]+ll[i-1])

ans=0
for i in range(m+1):
  if l_l[i]>k:
    break
  
  sm=0
  j=0
  while j<n and l_l[i]+sm+l[j]<=k:
    sm+=l[j]
    j+=1
  ans=max(ans,i+j)
print(ans)

### FIXED CODE ###

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

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])

ans, j = 0, M
for i in range(N + 1):
  if a[i] > K:
    break
  while b[j] > K - a[i]:
    j -= 1
  ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

n=int(input())
ai = list(map(int,input().split()))
kei = 0
last = 0
S = []
for i in range(0,n-1):
    for k in range(1,n-i):
      kei = ai[i]*ai[i+k]
      S.append(kei)
last = sum(S) % (10**9 + 7)      
print(last)

### FIXED CODE ###

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

for i in range(N):
    ans += A[i]*A[i]
last += sum(A)*sum(A)
last -= ans
last //= 2
print(last % 1000000007)
### BUGGY CODE ###

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

def main():
    N, M =  [int(i) for i in input().split()]
    cities = []
    for i in range(M):
        p, y = map(int, input().split())
        cities.append([p, y])

    dict = {}
    for p,y in cities:
        if p not in dict.keys():
            dict[p] = [y]
        else:
            dict[p].append(y)
    for p, y in cities:
        s = str(p).zfill(6) + str(sorted(dict[p]).index(y)+1).zfill(6)
        print(s)



if __name__ == "__main__":
    main()


### FIXED CODE ###

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

def main():
    N, M =  [int(i) for i in input().split()]
    cities = []

    for i in range(M):
        p, y = map(int, input().split())
        cities.append([p, y, i])

    cities.sort()
    ans = []

    num = 0
    before = cities[0][0]

    for i in range(M):
        if before != cities[i][0]:
            num = 1
            before = cities[i][0]
        else:
            num += 1
        ans.append([cities[i][0], num, cities[i][2]])

    ans.sort(key=lambda x:x[2])
    for a in ans:
        s = str(a[0]).zfill(6) + str(a[1]).zfill(6)
        print(s)



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

N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    ans = 0
else:
    for a in A:
        ans *= a
    if ans > 1000000000000000000:
        ans = -1
print(ans)

### FIXED CODE ###

def main():
    N =int(input())
    A =list(map(int,input().split()))
    if 0 in A:
        print(0)
        return
    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main()
### BUGGY CODE ###

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

x = 1
for i in range(n):
    x *= a[i]

if x > 1e18:
    print(-1)
else:
    print(x)


### FIXED CODE ###

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

x = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        x *= a[i]
        if x > 1e18:
            print(-1)
            exit()
    print(x)
### BUGGY CODE ###

s = input()
n = int(input())
f = 0

for i in range(n):
    a = input()
    if a == "1":
        f += 1
    else:
        b,c,d = a.split()
        if f%2 == 0:
            if c == "1":
                s = d + s
            else:
                s = s + d
        else:
            if c == "1":
                s = s + d
            else:
                s = d + s

if f%2 == 1:
    print(s[::-1])
else:
    print(s)



### FIXED CODE ###

from collections import deque

s = deque(list(input()))
n = int(input())
f = True

for i in range(n):
    a = input()
    if a == "1":
        f = not f
    else:
        b,c,d = a.split()
        if f:
            if c == "1":
                s.appendleft(d)
            else:
                s.append(d)
        else:
            if c == "1":
                s.append(d)
            else:
                s.appendleft(d)

if not f:
    s.reverse()

ans = "".join(s)
print(ans)
### BUGGY CODE ###

A,B,C,K = map(int,input().split())
count=0
for i in range(0,K):
    if A>0:
        count+=1
        A-=1
    elif A==0 and B>0:
        B -=1
    else:
        count-=1
print(count)



### FIXED CODE ###

A,B,C,K = map(int,input().split())
count=0

if K<=A:
    print(K)

elif A<K and K<B:
    print(A)

else:
    print(A-(K-A-B))
### BUGGY CODE ###

import copy

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    tmp = copy.deepcopy(A)
    tmp.remove(A[i])
    print(max(tmp))    


### FIXED CODE ###

import copy

N = int(input())
A = [int(input()) for _ in range(N)]

res = sorted(A,reverse=True)
for i in range(N):
    if A[i] == res[0]:
        print(res[1])
    else:
        print(res[0])
### BUGGY CODE ###

from fractions import gcd

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

g=A[0]
l=A[0]
for i in range(N):
    g=gcd(l,A[i])
    l=l*A[i]//g
    
ans=0
mod=10**9+7

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

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

a = list(map(int,input().split()))
A = a[0]
B = a[1]
K = a[2]
for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        pass
print(A,end=" ")
print(B)


### FIXED CODE ###

a = list(map(int,input().split()))
A = a[0]
B = a[1]
K = a[2]
A1 = A - K
B1 = B
if A1 < 0:
    B1 = A1 + B
    A1 = 0
    if B1 < 0:
        B1 = 0

print(A1,end=" ")
print(B1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))

    @lru_cache(maxsize=10000)
    def rec(h):
        if h <= 0:
            return 0
        return min(rec(h - a) + b for a, b in AB)

    print(rec(H))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,N=mis()
    AB = tuple(tuple(mis()) for _ in range(N))
    DP = [INF] * (H+1)
    DP[0] = 0
    for h in range(1, H+1):
        for i in range(N):
            DP[h] = min(DP[h], (DP[h-AB[i][0]]+AB[i][1] if h-AB[i][0]>0 else AB[i][1]))

    print(DP[-1])

main()
### BUGGY CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

maxV = 0
for i in range(2**N):
    bit = i
    X = Y = 0
    for j in range(N):
        mod = bit%2
        bit = bit//2
        if(mod==1):
            X += V[j]
            Y += C[j]
    maxV = max(maxV, X-Y)

print(maxV)


### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

X = [max(0, V[i]-C[i]) for i in range(N)]
print(sum(X))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc089/tasks/abc089_d

H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())
L=[0]*Q
R=[0]*Q
    
d=dict()
j=0
for b in A:
    for c in b:
        d[c]=j
        j +=1

for i in range(Q):
    L,R = map(int,input().split())
    ans = 0
    
    while L!=R: 
        tmp = d[L]
        p = tmp//W
        q = tmp %W
        L += D
        tmp2 = d[L]
        r = tmp2//W
        s = tmp2 %W
        #print(p,q,r,s)
        ans += abs(r-p) + abs(s-q)
    print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc089/tasks/abc089_d

def calc(x):
    if x<D+1:
        mv[x]=0
        return 0
    else:
        p = d[x][0]
        q = d[x][1]
        r = d[x-D][0]
        s = d[x-D][1]
        tmp = abs(p-r)+abs(q-s)
        ret= tmp+calc(x-D)
        mv[x]=ret
        return ret
####################################################################
import sys 
sys.setrecursionlimit(10**5)
H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())

d=dict()
z=0
for a in A:
    for b in a:
        p = z//W
        q = z%W
        d[b]=(p,q)
        z+=1
        
mv=[0]*(H*W+1)
for i in range(D):
    calc(H*W-i)
    #print(H*W-i,calc(H*W-i))    
#print(mv)

L=[0]*Q
R=[0]*Q
for _ in range(Q):
    L,R=map(int,input().split())
    print(mv[R]-mv[L])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_L = [[] for _ in range(M+1)]
for _ in range(N):
    L,R = map(int,input().split())
    d_to_L[R-L+1].append(L)

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L in d_to_L[m]:
        x = L
        while x <= M:
            tree[x] += 1
            x += x & (-x)
        x = L+m
        while x <= M:
            tree[x] -= 1
            x += x & (-x)
        long -= 1
    s = long
    for x in range(m,M+1,m):
        while x:
            s += tree[x]
            x -= x & (-x)
    answer[m] = s

print('\n'.join(map(str, answer[1:])))


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict

N,M = map(int,input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
    L,R = map(int,input().split())
    d_to_LR[R-L+1].append((L,R))

def BIT_update(tree,x,value):
    while x <= M:
        tree[x] += value
        x += x & (-x)

def BIT_sum(tree,x):
    s = 0
    while x:
        s += tree[x]
        x -= x & (-x)
    return s

tree = [0] * (M+1) # BIT で管理。左にあるLの個数 - (R+1)の個数 → いくつの[L,R]に入っているか
long = N # 長すぎて自動回収できる
answer = [0] * (M+1)

for m in range(1,M+1):
    for L,R in d_to_LR[m]:
        BIT_update(tree,L,1)
        BIT_update(tree,R+1,-1)
        long -= 1
    answer[m] = sum(BIT_sum(tree,x) for x in range(m,M+1,m)) + long

print('\n'.join(map(str, answer[1:])))
### BUGGY CODE ###

import math

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

ans = 0
while(len(A) > 0):
    a = A[0]
    A = A[1:]
    for i in range(len(A)):
        if math.log2(A[i] + a).is_integer():
            ans += 1
            A.pop(i)
            break

print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
c = Counter(A)

ans = 0
for a in A:
    b = (1 << a.bit_length()) - a
    if a == b and c[a] > 1:
        c[a] -= 2
        ans += 1
    elif a != b and c[a] > 0 and c[b] > 0:
        c[a] -= 1
        c[b] -= 1
        ans += 1

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

N, W = [int(x) for x in input().split()]
w = []
v = []

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        a = dp[i - 1][j]
        b = (dp[i - 1][j - w[i - 1]] + v[i - 1]) if j - w[i - 1] >= 0 else 0
        dp[i][j] = max(a, b)

print(dp[N][W])


### FIXED CODE ###

N, W = [int(x) for x in input().split()]
w = []
v = []

for _ in range(N):
    a, b = [int(x) for x in input().split()]
    w.append(a)
    v.append(b)

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(W + 1):
        a = dp[i - 1][j]
        b = (dp[i - 1][j - w[i - 1]] + v[i - 1]) if j - w[i - 1] >= 0 else 0
        dp[i][j] = max(a, b)

print(dp[N][W])
### BUGGY CODE ###

import itertools
import math
from functools import reduce

n, k = map(int, input().split())
mod = 10 ** 9 + 7

cnt = 0
for i in range(k, n + 1):
    sum_list = set()
    for pattern in list(itertools.combinations(range(n + 1), i)):
        result = reduce(lambda sum, val : sum + val, pattern, 0)
        sum_list.add(result)
    cnt += len(sum_list)

print(cnt + 1)

### FIXED CODE ###

import itertools
import math
from functools import reduce

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

pattern = 0

for i in range(k, n + 2):
    min = i * (0 + i - 1) // 2
    max = i * (n + n - i + 1) // 2
    pattern += max - min + 1
    
pattern %= 10 ** 9 + 7
    
print(pattern)