D - Welcome to Tokyo! Editorial /

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 2000 点

問題文

1 から M までの番号のついた M 人の競技プログラマーがおり，今日から N 日間の間に東京を訪れます． 競技プログラマー i は，L_i 日目から R_i 日目まで (1 \leq L_i \leq R_i \leq N) 東京に滞在します．

maroon 君は彼らとの食事会を計画しています． x 日目 (1 \leq x \leq N) に食事会を開催すると，L_i \leq x \leq R_i を満たすすべての競技プログラマー i と友達になることができます．

各 k=1,2,\cdots,N について，以下の問題を解いてください．

  • ちょうど k 回の食事会を開催する場合，友達になることができる競技プログラマーの人数の最大値を求めよ．

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^6
  • 1 \leq L_i \leq R_i \leq N
  • 入力される値はすべて整数．

入力

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

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

出力

N 行出力せよ． i 行目には k=i に対する答えを出力せよ．

入力例 1

3 3
1 1
1 2
3 3

出力例 1

2
3
3
  • k=1: 1 日目に食事会を開催すると，競技プログラマー 1,2 と友達になることができます．
  • k=2: 1,3 日目に食事会を開催すると，競技プログラマー 1,2,3 と友達になることができます．
  • k=3: 1,2,3 日目に食事会を開催すると，競技プログラマー 1,2,3 と友達になることができます．

入力例 2

4 4
1 1
2 2
3 3
4 4

出力例 2

1
2
3
4

入力例 3

3 6
1 1
1 2
1 2
2 3
2 3
3 3

出力例 3

4
6
6

入力例 4

20 15
15 19
1 8
6 11
3 11
11 17
6 6
16 20
7 11
11 14
2 19
1 3
7 7
6 19
14 15
15 15

出力例 4

7
11
12
13
14
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15

Score : 2000 points

Problem Statement

There are M competitive programmers (kyopro-ers) numbered 1 to M, who will visit Tokyo during the N days starting today. Kyopro-er i will stay in Tokyo from the L_i-th day through the R_i-th day (1 \leq L_i \leq R_i \leq N).

Maroon is planning dinner parties with them. If a dinner party is held on the x-th day (1 \leq x \leq N), he can make friends with all kyopro-ers i with L_i \leq x \leq R_i.

For each k=1,2,\cdots,N, solve the following problem.

  • Find the maximum number of kyopro-ers Maroon can make friends with if he holds exactly k dinner parties.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq 10^6
  • 1 \leq L_i \leq R_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Print N lines. The i-th line should contain the answer for k=i.

Sample Input 1

3 3
1 1
1 2
3 3

Sample Output 1

2
3
3
  • k=1: If he holds a party on the 1-st day, he can make friends with kyopro-ers 1 and 2.
  • k=2: If he holds a party on the 1-st and 3-rd days, he can make friends with kyopro-ers 1, 2, and 3.
  • k=3: If he holds a party on the 1-st, 2-nd, and 3-rd days, he can make friends with kyopro-ers 1, 2, and 3.

Sample Input 2

4 4
1 1
2 2
3 3
4 4

Sample Output 2

1
2
3
4

Sample Input 3

3 6
1 1
1 2
1 2
2 3
2 3
3 3

Sample Output 3

4
6
6

Sample Input 4

20 15
15 19
1 8
6 11
3 11
11 17
6 6
16 20
7 11
11 14
2 19
1 3
7 7
6 19
14 15
15 15

Sample Output 4

7
11
12
13
14
15
15
15
15
15
15
15
15
15
15
15
15
15
15
15