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 = "# instead of AVLTree\nclass BITbisect():\n    def __init__(self, max):\n        self.max = max\n        self.data = [0]*(self.max+1)\n    \n    # 0からiまでの区間和\n    # 立っているビットを下から処理\n    def query_sum(self, i):\n        s = 0\n        while i > 0:\n            s += self.data[i]\n            i -= i & -i\n        return s\n\n    # i番目の要素にxを足す\n    # 覆ってる区間すべてに足す\n    def add(self, i, x):\n        while i <= self.max:\n            self.data[i] += x\n            i += i & -i\n\n    def insert(self, x):\n        self.add(x, 1)\n\n    def delete(self, x):\n        self.add(x, -1)\n\n    def count(self, x):\n        return self.query_sum(x) - self.query_sum(x-1)\n    \n    def length(self):\n        return self.query_sum(self.max)\n    \n    # 下からc番目(0-indexed)の数\n    # O(log(N))\n    def search(self, c):\n        c += 1\n        s = 0\n        ind = 0\n        l = self.max.bit_length()\n        for i in reversed(range(l)):\n            if ind + (1<<i) <= self.max:\n                if s + self.data[ind+(1<<i)] < c:\n                    s += self.data[ind+(1<<i)]\n                    ind += (1<<i)\n        if ind == self.max:\n            return False\n        return ind + 1\n    \n    def bisect_right(self, x):\n        return self.query_sum(x)\n\n    def bisect_left(self, x):\n        if x == 1:\n            return 0\n        return self.query_sum(x-1)\n\n    # listみたいに表示\n    def display(self):\n        print('inside BIT:', end=' ')\n        for x in range(1, self.max+1):\n            if self.count(x):\n                c = self.count(x)\n                for _ in range(c):\n                    print(x, end=' ')\n        print()\n\nimport sys\ninput = sys.stdin.readline\n\nbase = 10**9\n\nN, M = map(int, input().split())\nPairs = [[] for _ in range(M+1)]\nfor _ in range(N):\n    a, b = map(int, input().split())\n    Pairs[b-a+1].append(a*base+b)\n\nansbit = BITbisect(M+1)\nusingbit = BITbisect(M+1)\n\nfor length, inPairs in enumerate(Pairs):\n    if length==0: continue\n\n    ansbit.add(1, len(inPairs))\n    ansbit.add(length+1, -len(inPairs))\n\n    rem = M//length\n    c = 0\n    for r in range(1, rem+1):\n        c += usingbit.query_sum(r*length)\n    ansbit.add(length, c)\n    ansbit.add(length+1, -c)\n\n    for p in inPairs:\n        l = p//base\n        r = p%base\n        usingbit.add(l, 1)\n        usingbit.add(r+1, -1)\n    \nfor n in range(1, M+1):\n    print(ansbit.query_sum(n))"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18331