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 Bit:\n    def __init__(self, n):\n        """\n        :param n: number of elements\n        """\n        self.n = n\n        self.tree = [0]*(n+1)\n        self.depth = n.bit_length() - 1\n\n    def sum(self, i):\n        """ return summation of elements in [0,i) """\n        s = 0\n        i -= 1\n        while i >= 0:\n            s += self.tree[i]\n            i = (i & (i + 1) )- 1\n        return s\n\n    def build(self, array):\n        """ bulid BIT from array """\n        for i, a in enumerate(array):\n            self.add(i, a)\n\n    def add(self, i, x):\n        """ add x to i-th element """\n        while i < self.n:\n            self.tree[i] += x\n            i |= i + 1\n\n    def get(self, i, j):\n        """ return summation of elements in [i,j) """\n        if i == 0:\n            return self.sum(j)\n        return self.sum(j) - self.sum(i)\n\n    def lower_bound(self, x, equal=False):\n        """\n        return tuple = (return maximum i s.t. a0+a1+...+ai < x (if not existing, -1 ) , a0+a1+...+ai )\n        if one wants to include equal (i.e., a0+a1+...+ai <= x), please set equal = True\n        (Cation) We must assume that A_i>=0\n        """\n        sum_ = 0\n        pos = -1    # 1-indexed の時は pos = 0\n        if not equal:\n            for i in range(self.depth, -1, -1):\n                k = pos + (1 << i)\n                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n\n                    sum_ += self.tree[k]\n                    pos += 1 << i\n        if equal:\n            for i in range(self.depth, -1, -1):\n                k = pos + (1 << i)\n                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n\n                    sum_ += self.tree[k]\n                    pos += 1 << i\n        return pos, sum_\n\n    def __getitem__(self, i):\n        """ [a0, a1, a2, ...] """\n        return self.get(i, i+1)\n\n    def __iter__(self):\n        """ [a0, a1, a2, ...] """\n        for i in range(self.n):\n            yield self.get(i, i+1)\n\n    def __str__(self):\n        text1 = " ".join(["element:            "] + list(map(str, self)))\n        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))\n        return "\\n".join((text1, text2))\n\nclass BitImos:\n    def __init__(self, n):\n        self.n = n\n        self.p = Bit(self.n + 1)\n        self.q = Bit(self.n + 1)\n\n    def add(self, s, t, x):\n        """ add x to a close-interval [s,t]"""\n        t += 1\n        self.p.add(s, -x * s)\n        self.p.add(t, x * t)\n        self.q.add(s, x)\n        self.q.add(t, -x)\n\n    def sum(self, s, t):\n        """ return summation of elements in [s,t) """\n        return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s\n\n    def __getitem__(self, s):\n        """ return s-th element of array (not sum-array) """\n        return self.q.sum(s+1)\n\n    def __iter__(self):\n        """ max(self) returns what we obtain by the Imos method"""\n        for t in range(self.n):\n            yield self.q.sum(t+1)\n\n    def __str__(self):\n        text1 = " ".join(["element: "] + list(map(str, self)))\n        return text1\n\n#############################################################\nimport sys\ninput = sys.stdin.readline\n\nN,M=map(int, input().split())\ndata=[[] for _ in range(M+1)]\nfor _ in range(N):\n    l,r=map(int, input().split())\n    data[r-l+1].append((l,r))\nB=BitImos(M+1)\nres=[0]*M\ncnt=N\nfor d in range(1,M+1):\n    for l,r in data[d]:\n        B.add(l,r,1)\n        cnt-=1\n    res[d-1]+=cnt\n    for i in range(0,M+1,d):\n        res[d-1]+=B[i]\nprint(*res,sep="\\n")'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 21175