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


def warshall_floyd(cost):
    ret = [[1]*N for _ in [0]*N]
    for k in range(N):
        for i, c_left in enumerate(cost[i][k] for i in range(N)):
            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):
                if c_left + c_right < c_now:
                    print(-1)
                    exit()
                if i == j or j == k or k == i:
                    continue
                if c_left + c_right == c_now:
                    ret[i][j] = ret[j][i] = 0
    return ret


INF = 10**10
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*N)


E = []
for i in range(N):
    for j in range(i+1, N):
        E.append((A[i][j], i, j))
E.sort()

road = warshall_floyd(A)
ans = 0
for cost, i, j in E:
    if not road[i][j]:
        continue
    ans += cost

print(ans)


### FIXED CODE ###


def warshall_floyd(cost):
    ret = [[1]*N for _ in [0]*N]
    for k in range(N):
        for i, c_left in enumerate(cost[i][k] for i in range(N)):
            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):
                if c_left + c_right < c_now:
                    print(-1)
                    exit()
                if i == j or j == k or k == i:
                    continue
                if c_left + c_right == c_now:
                    ret[i][j] = ret[j][i] = 0
    return ret


INF = 10**10
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*N)


E = []
for i in range(N):
    for j in range(i+1, N):
        E.append((A[i][j], i, j))
E.sort()

road = warshall_floyd(A)
ans = 0
for cost, i, j in E:
    if not road[i][j]:
        continue
    ans += cost

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

import collections
S = input()

a = []
s = int(S[-1])
for i in range(2,len(S)+1):
    s += int(S[-i])*(10**(i-1))
    #print(s)
    a.append(s%2019)

A = collections.Counter(a)
#print(A)

ans = 0
for i in A.values():
    if i>=2:
        ans += int(i*(i-1)/2)

ans += A[0]
print(ans)

### FIXED CODE ###

S = input()
dp = [0 for i in range(2019)]
dp[0] = 1

num = 0
for i,j in enumerate(S[::-1]):
    num += int(j)*(pow(10,i,2019))
    dp[num%2019] += 1

ans = 0
for m in dp:
    if m >= 2:
        ans += int(m*(m-1)/2)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-k+1):
    e = 0
    for j in range(0,k):
        e += (0.5*(p[i+j]+1))
    ans = max(ans,e)
print(ans)


### FIXED CODE ###

import numpy as np
n, k = map(int,input().split())
p = list(map(int,input().split()))

e = [(i+1)/2 for i in p]
e = np.cumsum(e)
e = np.append(0,e)
ans = 0
for i in range(n-k+1):
    ans = max(e[i+k]-e[i],ans)
print(ans)
### BUGGY CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = []
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    while p < N and List[p][0] == i:
        List_S.append(List[p][1])
        p += 1
        add = 1
    if len(List_S) != 0:
        if add == 1:
            List_S.sort()
        result += List_S.pop()
 
print(result)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline

N, M = map(int,input().split()) # 複数の数字を変数に格納
List = [list(map(int,input().split())) for i in range(N)] # [[1,2],[3,4],[5,6]]

List.sort(key=itemgetter(0))
List_S = [0]
 
result = 0
p = 0

for i in range(1, M+1):
    add = 0
    add_list = []
    while p < N and List[p][0] == i:
        if List_S[len(List_S)-1] < List[p][1]:            
            List_S.append(List[p][1])
        else:
            add_list.append(List[p][1])
            add += 1
        p += 1
            
    if len(List_S) != 1:
        result += List_S.pop()
        if add > 0:
            List_S.extend(add_list)
            List_S.sort()
 
print(result)
### BUGGY CODE ###

s = input()
K = int(input())

from heapq import heappush, heappop

Q = set()
u = set()
N = len(s)
for i in range(N):
    for j in range(i+1, N+1):
        ss = s[i:j]
        if ss in u:
            continue
        u.add(ss)
        Q.add(ss)
        if len(Q) > K:
            Q.remove(max(Q))
l = sorted(Q)
print(l[K-1])


### FIXED CODE ###

s = input()
K = int(input())

from heapq import heappush, heappop

Q = set()
u = set()
N = len(s)
for i in range(N):
    for j in range(i+1, i+K+1):
        ss = s[i:j]
        if ss in u:
            continue
        u.add(ss)
        Q.add(ss)
        if len(Q) > K:
            Q.remove(max(Q))
l = sorted(Q)
print(l[K-1])
### BUGGY CODE ###

n = int(input())
l_list = list(map(int,input().split()))
l_list.sort(reverse=True)
ans = 0
for i in range(n):
  a = l_list[i]
  for j in range(i+1,n):
    for k in range(j+1,n):
      if a < l_list[j]+l_list[k]:
        ans += 1
print(ans)

### FIXED CODE ###

#関数を持ってくる
from bisect import bisect_left
#入力
n = int(input())
l_list = list(map(int,input().split()))
#ソート
l_list.sort()
#答えの数を数えるものを作る
ans = 0
#三角形の中で一番短い辺aに対して
for i in range(n-2):
  a = l_list[i]
  #2番目に短い辺bが存在し
  for j in range(i+1,n-1):
    b = l_list[j]
    #一番長い辺cの下限値であるa+bのリスト内で入る位置x
    x = bisect_left(l_list,a+b)
    #cとして考えられる値はjとxの間の個数
    ans += x-j-1
print(ans)
### BUGGY CODE ###

import bisect
N,M=[int(i) for i in input().split()]
A = sorted([int(i) for i in input().split()])
for i in range(M):
  A2=A[N-1]//2
  A.pop(N-1)
  bisect.insort_left(A,A2)
print(sum(A))

### FIXED CODE ###

import heapq
N,M=[int(i) for i in input().split()]
A=sorted([-int(i) for i in input().split()])
for i in range(M):heapq.heappush(A,-(-heapq.heappop(A)//2))
print(-sum(A))
### BUGGY CODE ###

import itertools

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

count = 0
for i in range(1, n+1):
    for c in itertools.combinations(xs, i):
        if sum(c) == a * i:
            count += 1

print(count)

### FIXED CODE ###

import itertools

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

dp = [[[0 for _ in range(a * n + 1)] for _ in range(n + 1)]
      for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        for k in range(a * n + 1):
            dp[i][j][k] = dp[i-1][j][k]
            if j > 0 and k - xs[i-1] >= 0:
                dp[i][j][k] += dp[i-1][j-1][k-xs[i-1]]


c = 0
for j in range(1, n+1):
    c += dp[n][j][j * a]

print(c)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(A: int, B: int, N: int):
    m = -1
    for i in range(N+1):
        x = i
        m = max([m, int((A*x)/B) - A * int(x/B)])
    return m


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    # N = pow(10, 9)
    print(solve(A, B, N))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(A: int, B: int, N: int):
    if A == 1: return 0

    if N < B:
        x = N
    else:
        md = N % B
        x = int(N - (md + 1))
    return int((A*x)//B) - A * int(x//B)

    # m = -1
    # for i in range(N+1):
    #     x = i
    #     m = max([m, int((A*x)/B) - A * int(x/B)])
    # return m


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    # N = pow(10, 9)
    print(solve(A, B, N))

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

import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 2*H*W
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))  

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

import collections

n = int(input())
a = [collections.deque(map(lambda s: int(s) - 1, input().split())) for _ in range(n)]

def f():
    day = 0
    players = set(range(n))

    while players:
        visited = set()
        removals = set()
        for i in players:
            if i in visited:
                continue
            
            x = a[i][0] # iの次候補
            if x in visited:
                continue

            y = a[x][0] # xの次候補
            if i == y:
                a[i].popleft()
                a[x].popleft()
                visited.add(i)
                visited.add(x)
                if not a[i]:
                    removals.add(i)
                if not a[x]:
                    removals.add(x)

        if visited:
            players -= removals
            day += 1
        else:
            return -1

    return day



print(f())

### FIXED CODE ###

import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)
### BUGGY CODE ###

N = int(input())
S = list(input())

ans = []
for i in range(N):
    count = 0
    for j in range(N):
        if i > j:
            if S[j] == 'W':
                count += 1
        elif i < j: 
            if S[j] == 'E':
                count +=1
        else:
            pass
    ans.append(count)
print(min(ans))

### FIXED CODE ###

N = int(input())
S = input()

ans = S.count('E')
w = 0
e = S.count('E')
for i in range(N):
    if S[i-1] == 'W' and i != 0:
        w += 1
    if S[i] == 'E':
        e -= 1
    if w + e < ans:
        ans = w + e
print(ans)
### BUGGY CODE ###

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

fromR = {i:[] for i in range(N+1)}
toR = {i:[] for i in range(N+1)}

ans = [-1 for i in range(N+1)]

for _ in range(N-1+M):
    a,b=map(int,input().split())
    fromR[a].append([b,a])
    toR[b].append(a)

r=1
while len(toR[r])>0:
    r=toR[r][0]

ans[r]=0

que = fromR[r]

while len(que)>0:
    tmp=[]
    for q in que:
        b,a=q
        flag=True
        for p in toR[b]:
            flag = flag and ans[p]!=-1
        if flag:
            ans[b]=a
            tmp+=fromR[b]
    que=tmp
for a in ans[1:]:
    print(a)


### FIXED CODE ###

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

fromR = {i:[] for i in range(N+1)}

cnt = [0 for i in range(N+1)]
ans = [-1 for i in range(N+1)]

for _ in range(N-1+M):
    a,b=map(int,input().split())
    fromR[a].append([b,a])
    cnt[b]+=1
r=-1
for i in range(1,N+1):
    if cnt[i]==0:
        r=i
        break

ans[r]=0

que = fromR[r]

while len(que)>0:
    tmp=[]
    for q in que:
        b,a=q
        cnt[b]-=1
        if cnt[b]==0:
            ans[b]=a
            tmp+=fromR[b]
    que=tmp
for a in ans[1:]:
    print(a)
### BUGGY CODE ###

s = input().rstrip()
res = 0
for i in range(len(s)):
    if s[i] == 'A':
        res -= i - 1
        break
for i in range(len(s)):
    if s[::-1][i] == 'Z':
        res += len(s) - 1 - i
        break
print(res)

### FIXED CODE ###

s = input().rstrip()
ss = s[::-1]
n = len(s)
res = 0
for i in range(n):
    if s[i] == 'A':
        res -= i - 1
        break
for i in range(n):
    if ss[i] == 'Z':
        res += n - 1 - i
        break
print(res)
### BUGGY CODE ###

import collections

n=int(input())
aa=[input() for aa in range(n)]

myset=list(set(aa))
#print(myset)

mycount=0
for bb in myset:
    tmp=aa.count(bb)
    if tmp%2==1:
        mycount+=1

print(mycount)

### FIXED CODE ###

from collections import Counter

n=int(input())

mylist=[input() for aa in range(n)]
#print(aa)

data=Counter(mylist)
val=list(data.values())
val=[1 for aa in val if aa%2==1]
print(sum(val))
### BUGGY CODE ###

from fractions import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = (pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W)) - 2) % MOD
print(pow(ans, ga*gb, MOD))


### FIXED CODE ###

from fractions import gcd
MOD = 10**9 + 7
H, W, T = map(int, input().split())
ga, gb = gcd(H, T), gcd(W, T)
H //= ga
W //= gb
ans = (pow(2, H, MOD) + pow(2, W, MOD) - 1 + pow(2, gcd(H, W)) - 2) % MOD
print(pow(ans, ga*gb, MOD))
### BUGGY CODE ###

S = input()[::-1]
S_len = len(S)  # <= 200000
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
for s in S:
    val = s + val
    dp[int(val) % 2019] += 1
for i in dp:
    ans += i * (i-1) // 2
print(ans)


### FIXED CODE ###

S = input()[::-1]
ans = 0
dp = [0] * 2019
dp[0] = 1
val = ''
m = 0
x_10 = 1
for s in S:
    m = (m + int(s) * x_10) % 2019
    dp[m] += 1
    x_10 = (x_10 * 10) % 2019
for i in dp:
    ans += i * (i-1) // 2
print(ans)
### BUGGY CODE ###

def main():
    N=int(input())
    AB=[0]*N
    for i in range(N):
        AB[i]=list(map(int,input().split()))
    AB.sort()
    count=AB[-1][0]
    while AB[-1][1]-1>=0:
        AB[-1][1]-=1
        count+=1
    print(count)
if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N=int(input())
    AB=[0]*N
    for i in range(N):
        AB[i]=list(map(int,input().split()))
    AB.sort()
    count=AB[-1][0]
    count+=AB[-1][1]
    print(count)
if __name__=="__main__":
    main()
### BUGGY CODE ###

a = input().split()
a = [int(i) for i in a]
query = []
citydict = dict()
for i in range(a[1]):
	temp = input().split()
	temp = [int(i) for i in temp]
	query.append(temp)
	if temp[0] not in citydict:
		citydict[temp[0]] = [temp[1]]
	else:
		citydict[temp[0]].append(temp[1])
		
for i in citydict:
	citydict[i] = sorted(citydict[i])
	
for i in query:
	print ("%06d%06d" % (i[0],citydict[i[0]].index(i[1]) + 1))

### FIXED CODE ###

a = input().split()
a = [int(i) for i in a]
query = []
citydict = dict()
for i in range(a[1]):
	temp = input().split()
	temp = [int(i) for i in temp]
	query.append(temp)
	try:
		citydict[temp[0]].append(temp[1])
	except:
		citydict[temp[0]] = [temp[1]]
		
indexdict = dict()
for i in citydict:
	citydict[i] = sorted(citydict[i])
	indexdict[i] = dict()
	for j in range(len(citydict[i])):
		indexdict[i][citydict[i][j]] = j
		
for i in query:
	print ("%06d%06d" % (i[0],indexdict[i[0]][i[1]] + 1))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque
    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    while que:
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W:
                    que.append((nxh,nxw,worp))
            
            for i in range(-2,3,1):
                for j in range(-2,3,1):
                    nxh,nxw = h+i,w+j
                    if 0<=nxh < H and 0<=nxw < W:
                        que.append((nxh,nxw,worp+1))
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()

### FIXED CODE ###

"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    nxQue = deque([])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    INF = 10**13
    for _ in range(INF):
        if not que:
            if nxQue:
                que = nxQue
                nxQue = deque([])
                continue
            else:
                break
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    if b == 0:
                        for i in range(a,a*3,a):
                            for j in range(-2,3,1):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
                    else:
                        for i in range(-2,3,1):
                            for j in range(b,b*3,b):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()
### BUGGY CODE ###

#!/usr/bin/env python3

import itertools

N, M, Q = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N
lis_2 = []

for i in itertools.permutations(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    if j in lis_2:
        continue
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)
    lis_2.append(j)

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import itertools

N, M, Q = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]

for i in itertools.combinations_with_replacement(X, r=N):
    cnt = 0
    j = list(i)
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

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

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

    def add(self, k, x):
        while k <= self.n:
            self.bit[k] += x
            k += k & -k

    def sum(self, k):
        s = 0
        while k > 0:
            s += self.bit[k]
            k -= k & -k
        return s


n, m = map(int, input().split())
st = BIT(m)
L, R = [], []
d = [[] for i in range(m + 1)]
for i in range(n):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    d[r - l + 1].append(i)

num = n
for i in range(1, m + 1):
    num -= len(d[i])
    for j in d[i]:
        st.add(L[j], 1)
        st.add(R[j] + 1, -1)

    tmp = 0
    k = i
    for j in range(k, m + 1, i):
        tmp += st.sum(j)

    print(num + tmp)


### FIXED CODE ###

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

    def add(self, k, x):
        while k <= self.n:
            self.bit[k] += x
            k += k & -k

    def sum(self, k):
        s = 0
        while k > 0:
            s += self.bit[k]
            k -= k & -k
        return s


n, m = map(int, input().split())
st = BIT(m)
L, R = [], []
d = [[] for i in range(m + 1)]
for i in range(n):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    d[r - l + 1].append(i)

num = n
for i in range(1, m + 1):
    num -= len(d[i])
    for j in d[i]:
        st.add(L[j], 1)
        st.add(R[j] + 1, -1)

    tmp = 0
    k = i
    for j in range(k, m + 1, i):
        tmp += st.sum(j)

    print(num + tmp)
### BUGGY CODE ###

s_l = list(input())
n = len(s_l)

anya = 100
ans = 0
flag = -1
for i in range(n-1,3,-1):
    for j in range(i-4,-1,-1):
        if flag > 0:
            flag -= 1
            continue
        val = int(''.join(s_l[j:i+1]))
        if val%2019 == 0 and val != 0:
            ans += 1
            flag = 4
        else:
            flag = -1
        if flag == 0:
            anya = 0
    if anya == 0:
        break


print(ans)

### FIXED CODE ###

s_l = list(input())
n = len(s_l)

# 公式解説参照
dp_dict = {0:1}
t = 0
for i in range(n):
    a = int(s_l[-(i+1)])
    t = (t + a*(pow(10,i,2019)))%2019
    dp_dict[t] = dp_dict.get(t,0) + 1

ans = 0
for val in dp_dict.values():
    ans += val*(val-1)//2

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

n=int(input())
ans=1
a=list(map(int,input().split()))
for i in range(n):
    ans*=a[i]
if ans>1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
flag=0
ans=0
if 0 in a:
    flag=1
if flag==0:
    ans=1
    for i in range(n):
        ans*=a[i]
        if ans>1000000000000000000:
            flag=-1
            break
if flag==-1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
list = [int(e) for e in input().split()]
set = set(list)

for i in range(1,n+1):
    if i in set:
        print(list.count(i))
        del list[0:list.count(i)]
    else:
        print(0)

### FIXED CODE ###

n = int(input())
list = [int(e) for e in input().split()]

import collections
list2 = collections.Counter(list)

for i in range(1,n+1):
    print(list2[i])