행운의 추첨 2

시간 제한5초메모리 제한1024 MB

요약

1부터 m까지의 정수 중 K개를 골라 적어도 하나의 점을 포함하는 구간 [A, B]의 최대 개수를 각 K마다 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 구간
정답자: 아직 제출이 없습니다

문제

ICPC 위원회는 참가 팀을 응원하기 위해 깜짝 이벤트를 준비한다. 위원회는 대회 전에 각 팀에게 두 수 $A$ 와 $B$ ( $1 \le A \le B \le m$ )로 이루어진 쌍을 준다. 이 쌍은 대회가 끝난 뒤 행운의 추첨에 쓰인다.

위원회는 추첨을 $K$ 번 진행하려 한다. 각 추첨에서 위원회가 수 $C$ 를 하나 고르면, $A \le C \le B$ 를 만족하는 쌍 $(A, B)$ 를 가진 팀이 모두 당첨된다. 더 많은 팀을 기쁘게 하려고, 위원회는 $K$ 번의 추첨에 쓸 $K$ 개의 수를 미리 골라 당첨 팀이 가장 많아지도록 한다. 한 팀은 여러 번 당첨될 수 있지만 한 번만 당첨된 것으로 센다.

$K = 1, 2, \ldots, m$ 각각에 대해 당첨 팀 수의 최댓값을 출력하는 프로그램을 작성하라.

입력

첫 줄에 두 정수 $m$ 과 $n$ ( $1 \le m, n \le 1\,000\,000$ )이 주어진다. $m$ 은 팀에게 주는 수의 상한이고, $n$ 은 팀의 수이다. 이어서 $n$ 개의 줄에 각 팀의 쌍 $A$ 와 $B$ ( $1 \le A \le B \le m$ )가 주어진다.

출력

정확히 $m$ 개의 줄을 출력한다. $i$ 번째 줄에는 $K = i$ 일 때 당첨 팀 수의 최댓값을 출력한다. 여러 번 당첨된 팀은 한 번만 센다.

예제5

예제 1
입력
```
7 5
1 2
1 4
3 6
4 7
5 6
```
예상 출력
```
3
5
5
5
5
5
5
```
예제 2
입력
```
5 3
2 4
1 3
3 5
```
예상 출력
```
3
3
3
3
3
```
예제 3
입력
```
5 4
2 3
1 1
4 5
4 5
```
예상 출력
```
2
3
4
4
4
```

예제 4

입력

예상 출력

예제 5
입력
```
3 3
1 1
1 2
3 3
```
예상 출력
```
2
3
3
```