041 - Convenience Store 2 Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あるコンビニは時刻 0 に開店し、時刻 T に閉店します。このコンビニには N 人の従業員が働いており、i 番目 (1 \leq i \leq N) の従業員は時刻 L_i に出勤し、時刻 R_i に退勤します。

t = 0, 1, 2, \dots, T-1 それぞれについて、時刻 t+0.5 にコンビニにいる従業員の数を出力するプログラムを作成してください。

制約

  • 1 \leq T \leq 500\,000
  • 1 \leq N \leq 500\,000
  • 0 \leq L_i < R_i \leq T (1 \leq i \leq N)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

T
N
L_1 R_1
\vdots
L_N R_N

出力

全体で T 行出力してください。

t + 1 行目 (0 \leq t \leq T-1) には、時刻 t+0.5 にコンビニにいる従業員の数を出力してください。

入力例 1

10
7
0 3
2 4
1 3
0 3
5 6
5 6
5 6

出力例 1

2
3
4
1
0
3
0
0
0
0

このコンビニは時刻 0 に開店し、時刻 10 に閉店します。従業員の出退勤の様子を図に表すと以下のようになります。