E - At Least One Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 M および N 個の整数の組 (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N) が与えられます。
すべての i について 1 \leq A_i \lt B_i \leq M が成り立っています。

次の条件を満たす数列 S を良い数列と呼びます。

  • S は数列 (1,2,3,..., M) の連続部分列である。
  • すべての i について S は A_i, B_i の少なくとも一方を含んでいる。

長さ k の良い数列としてあり得るものの個数を f(k) とします。
f(1), f(2), \dots, f(M) を列挙してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq M
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

答えを以下の形式で出力せよ。

f(1) f(2) \dots f(M)

入力例 1

3 5
1 3
1 4
2 5

出力例 1

0 1 3 2 1

良い数列としてあり得るものを列挙すると次のようになります。

  • (1,2)
  • (1,2,3)
  • (2,3,4)
  • (3,4,5)
  • (1,2,3,4)
  • (2,3,4,5)
  • (1,2,3,4,5)

入力例 2

1 2
1 2

出力例 2

2 1

入力例 3

5 9
1 5
1 7
5 6
5 8
2 6

出力例 3

0 0 1 2 4 4 3 2 1

Score : 500 points

Problem Statement

You are given an integer M and N pairs of integers (A_1, B_1), (A_2, B_2), \dots, (A_N, B_N).
For all i, it holds that 1 \leq A_i \lt B_i \leq M.

A sequence S is said to be a good sequence if the following conditions are satisfied:

  • S is a contiguous subsequence of the sequence (1,2,3,..., M).
  • For all i, S contains at least one of A_i and B_i.

Let f(k) be the number of possible good sequences of length k.
Enumerate f(1), f(2), \dots, f(M).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \lt B_i \leq M
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Print the answers in the following format:

f(1) f(2) \dots f(M)

Sample Input 1

3 5
1 3
1 4
2 5

Sample Output 1

0 1 3 2 1

Here is the list of all possible good sequences.

  • (1,2)
  • (1,2,3)
  • (2,3,4)
  • (3,4,5)
  • (1,2,3,4)
  • (2,3,4,5)
  • (1,2,3,4,5)

Sample Input 2

1 2
1 2

Sample Output 2

2 1

Sample Input 3

5 9
1 5
1 7
5 6
5 8
2 6

Sample Output 3

0 0 1 2 4 4 3 2 1