Contest Duration: - (local time) (100 minutes) Back to Home
E - At Least One /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すべての i について 1 \leq A_i \lt B_i \leq M が成り立っています。

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

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)

3 5
1 3
1 4
2 5

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)

1 2
1 2

2 1

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)

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)

1 2
1 2

2 1

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

### Sample Output 3

0 0 1 2 4 4 3 2 1