Snuke has decided to play a game, where the player runs a railway company.
There are M+1 stations on Snuke Line, numbered 0 through M.
A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train.
For example, if d = 3, the train stops at station 0, 3, 6, 9, and so forth.
There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations l_i, l_i+1, l_i+2, ..., r_i.
There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, ..., M.
For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0.
Here, assume that it is not allowed to change trains.

-----Constraints-----
 - 1 ≦ N ≦ 3 × 10^{5}
 - 1 ≦ M ≦ 10^{5}
 - 1 ≦ l_i ≦ r_i ≦ M

-----Input-----
The input is given from Standard Input in the following format:
N M
l_1 r_1
:
l_{N} r_{N}

-----Output-----
Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.

-----Sample Input-----
3 3
1 2
2 3
3 3

-----Sample Output-----
3
2
2

 - If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.
 - If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.
 - If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'class lazy_segtree():\n    def update(self,k):self.d[k]=self.op(self.d[2*k],self.d[2*k+1])\n    def all_apply(self,k,f):\n        self.d[k]=self.mapping(f,self.d[k])\n        if (k<self.size):self.lz[k]=self.composition(f,self.lz[k])\n    def push(self,k):\n        self.all_apply(2*k,self.lz[k])\n        self.all_apply(2*k+1,self.lz[k])\n        self.lz[k]=self.identity\n    def __init__(self,V,OP,E,MAPPING,COMPOSITION,ID):\n        self.n=len(V)\n        self.log=(self.n-1).bit_length()\n        self.size=1<<self.log\n        self.d=[E for i in range(2*self.size)]\n        self.lz=[ID for i in range(self.size)]\n        self.e=E\n        self.op=OP\n        self.mapping=MAPPING\n        self.composition=COMPOSITION\n        self.identity=ID\n        for i in range(self.n):self.d[self.size+i]=V[i]\n        for i in range(self.size-1,0,-1):self.update(i)\n    def set(self,p,x):\n        assert 0<=p and p<self.n\n        p+=self.size\n        for i in range(self.log,0,-1):self.push(p>>i)\n        self.d[p]=x\n        for i in range(1,self.log+1):self.update(p>>i)\n    def get(self,p):\n        assert 0<=p and p<self.n\n        p+=self.size\n        for i in range(self.log,0,-1):self.push(p>>i)\n        return self.d[p]\n    def prod(self,l,r):\n        assert 0<=l and l<=r and r<=self.n\n        if l==r:return self.e\n        l+=self.size\n        r+=self.size\n        for i in range(self.log,0,-1):\n            if (((l>>i)<<i)!=l):self.push(l>>i)\n            if (((r>>i)<<i)!=r):self.push(r>>i)\n        sml,smr=self.e,self.e\n        while(l<r):\n            if l&1:\n                sml=self.op(sml,self.d[l])\n                l+=1\n            if r&1:\n                r-=1\n                smr=self.op(self.d[r],smr)\n            l>>=1\n            r>>=1\n        return self.op(sml,smr)\n    def all_prod(self):return self.d[1]\n    def apply_point(self,p,f):\n        assert 0<=p and p<self.n\n        p+=self.size\n        for i in range(self.log,0,-1):self.push(p>>i)\n        self.d[p]=self.mapping(f,self.d[p])\n        for i in range(1,self.log+1):self.update(p>>i)\n    def apply(self,l,r,f):\n        assert 0<=l and l<=r and r<=self.n\n        if l==r:return\n        l+=self.size\n        r+=self.size\n        for i in range(self.log,0,-1):\n            if (((l>>i)<<i)!=l):self.push(l>>i)\n            if (((r>>i)<<i)!=r):self.push((r-1)>>i)\n        l2,r2=l,r\n        while(l<r):\n            if (l&1):\n                self.all_apply(l,f)\n                l+=1\n            if (r&1):\n                r-=1\n                self.all_apply(r,f)\n            l>>=1\n            r>>=1\n        l,r=l2,r2\n        for i in range(1,self.log+1):\n            if (((l>>i)<<i)!=l):self.update(l>>i)\n            if (((r>>i)<<i)!=r):self.update((r-1)>>i)\n    def max_right(self,l,g):\n        assert 0<=l and l<=self.n\n        assert g(self.e)\n        if l==self.n:return self.n\n        l+=self.size\n        for i in range(self.log,0,-1):self.push(l>>i)\n        sm=self.e\n        while(1):\n            while(i%2==0):l>>=1\n            if not(g(self.op(sm,self.d[l]))):\n                while(l<self.size):\n                    self.push(l)\n                    l=(2*l)\n                    if (g(self.op(sm,self.d[l]))):\n                        sm=self.op(sm,self.d[l])\n                        l+=1\n                return l-self.size\n            sm=self.op(sm,self.d[l])\n            l+=1\n            if (l&-l)==l:break\n        return self.n\n    def min_left(self,r,g):\n        assert (0<=r and r<=self.n)\n        assert g(self.e)\n        if r==0:return 0\n        r+=self.size\n        for i in range(self.log,0,-1):self.push((r-1)>>i)\n        sm=self.e\n        while(1):\n            r-=1\n            while(r>1 and (r%2)):r>>=1\n            if not(g(self.op(self.d[r],sm))):\n                while(r<self.size):\n                    self.push(r)\n                    r=(2*r+1)\n                    if g(self.op(self.d[r],sm)):\n                        sm=self.op(self.d[r],sm)\n                        r-=1\n                return r+1-self.size\n            sm=self.op(self.d[r],sm)\n            if (r&-r)==r:break\n        return 0\nN,M=list(map(int,input().split()))\nseq=[]\nfor i in range(N):\n    l,r=list(map(int,input().split()))\n    seq.append((l,r+1))\nseq.sort(key=lambda x:x[1]-x[0])\nans=[0 for i in range(M+1)]\nadd=lambda x,y:x+y\nINF=10**9\nG=lazy_segtree([0 for i in range(M+1)],max,-INF,add,add,0)\nstack=seq[::-1]\nfor d in range(1,M+1):\n    while(len(stack)>0 and stack[-1][1]-stack[-1][0]<d):\n        l,r=stack[-1]\n        G.apply(l,r,1)\n        stack.pop()\n    ans[d]+=len(stack)\n    for i in range(0,M+1,d):\n        ans[d]+=G.get(i)\nfor i in range(1,M+1):\n    print((ans[i]))\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18467