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)


### 入力例 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