output_description: 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.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M
      l_1 r_1
      :
      l_{N} r_{N}
attempt: import sys
  
  input = sys.stdin.readline
  
  
  def main():
      n, m = map(int, input().split())
      LR = [list(map(int, input().split())) for _ in range(n)]
  
      BIT = [0] * (m + 2)
  
      def add(i, a):
          while i <= m + 1:
              BIT[i] += a
              i += i & (-i)
  
      def bit_sum(i):
          res = 0
          while i > 0:
              res += BIT[i]
              i -= i & (-i)
          return res
  
      for l, r in LR:
          add(l, 1)
          add(r + 1, -1)
  
      S = sorted([(r - l + 1, l, r) for l, r in LR])
      cnt = 0
      L = []
      for i in range(m, 0, -1):
          while S and S[-1][0] == i:
              c, l, r = S.pop()
              cnt += 1
              add(l, -1)
              add(r + 1, 1)
          res = cnt
          for j in range(0, m + 1, i):
              res += bit_sum(j)
          L.append(res)
      print(*L[::-1], sep="\n")
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  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.
samples: [{"input": "3 3\n    1 2\n    2 3\n    3 3", "output": "3\n    2\n    2\n    \n\n  * If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.\n  * If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.\n  * If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.\n\n* * *"}, {"input": "7 9\n    1 7\n    5 9\n    5 7\n    5 9\n    1 1\n    6 8\n    3 4", "output": "7\n    6\n    6\n    5\n    4\n    5\n    5\n    3\n    2"}]