#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

### Title

### Problem 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.

### 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:

NMl_{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 1

3 3 1 2 2 3 3 3

### Sample Output 1

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`.

### Sample Input 2

7 9 1 7 5 9 5 7 5 9 1 1 6 8 3 4

### Sample Output 2

7 6 6 5 4 5 5 3 2

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 100 | 39 | 1s | 256MB | Minimum |

2 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o souvenirs -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512