忆艾はこの学期に $n$ 門の授業を受ける必要がある。しかし、彼女はサボりたいため、授業を自分の分身に任せることにした。第 $i$ 門の授業には時間帯 $(l_i, r_i)$ が割り当てられている。もし憶艾がある分身に集合 $S$ に含まれる授業を割り当てる場合、それらの授業の時間帯が重ならないようにする必要がある。すなわち、任意の $i, j \in S (i \neq j)$ に対して、$(l_i, r_i) \cap (l_j, r_j) = \varnothing$ が成立しなければならない。
憶艾は、各 $k (1 \le k \le m)$ について、合計 $k$ 人の分身がいる場合に、彼らに任せることができる授業の最大数を求めたいと考えている。
入力
1行目に2つの正整数 $n, m$ が与えられる。それぞれ授業の数と分身の最大数を表す。
続く $n$ 行には、各授業の時間帯を表す2つの正整数 $l_i, r_i$ が与えられる。
出力
合計 $m$ 行を出力する。各行には、$k$ 人の分身が担当できる授業の最大数を $k=1$ から $k=m$ まで順に出力する。
入出力例
入出力例 1
6 3 1 5 5 10 1 2 3 4 6 7 8 9
出力例 1
4 6 6
小課題
すべてのデータにおいて、$1 \le m \le n \le 3 \times 10^5$、$1 \le l_i < r_i \le 10^9$ を満たす。
| テストケース番号 | $n$ | $m$ |
|---|---|---|
| $1$ | $100$ | $10$ |
| $2$ | $100$ | |
| $3$ | $1000$ | $1000$ |
| $4$ | $3000$ | $3000$ |
| $5$ | $10^5$ | $10$ |
| $6$ | $100$ | |
| $7$ | $10^5$ | |
| $8$ | $3\times 10^5$ | $10$ |
| $9$ | $100$ | |
| $10$ | $3\times 10^5$ |