牛たちは面白い新しいゲームを考案しようと努力しています。現在の取り組みの一つでは、$N$ 個の区間（$1\le N\le 2\cdot 10^5$）を使います。$i$ 番目の区間は数直線上の位置 $a_i$ から始まり、位置 $b_i \geq a_i$ で終わります。$a_i$ と $b_i$ はどちらも範囲 $0 \ldots M$ の整数で、$1 \leq M \leq 5000$ です。

ゲームでは、Bessie が一つの区間（例えば $i$ 番目）を選び、いとこの Elsie も一つの区間（例えば $j$ 番目、Bessie と同じでも構いません）を選びます。ある値 $k$ に対して、$a_i + a_j \leq k \leq b_i + b_j$ なら二頭は勝ちます。

範囲 $0 \ldots 2M$ の各 $k$ について、Bessie と Elsie が勝てる順序付き対 $(i,j)$ の数を求めてください。

入力

入力の最初の行に $N$ と $M$ が与えられます。続く $N$ 行では、それぞれ整数 $a_i$ と $b_i$ によって一つの区間が記述されます。

出力

範囲 $0 \ldots 2M$ の各 $k$ に対応する答えを、合計 $2M+1$ 行に出力してください。

入出力例

入力 1

2 5
1 3
2 5

出力 1

0
0
1
3
4
4
4
3
3
1
1

注記

この例で $k=3$ の場合だけを考えると、Bessie と Elie が勝てる順序付き対は $(1, 1)$、$(1, 2)$、$(2, 1)$ の三つです。

小課題

• テストケース 1-2 は $N\le 100, M\le 100$ を満たします。

• テストケース 3-5 は $N\le 5000$ を満たします。

• テストケース 6-20 に追加の制約はありません。

出力する値は 32 ビット整数に収まらないほど大きくなる場合があるので、64 ビット整数（例えば C や C++ の "long long" 整数）を使うとよいでしょう。

問題作成者：Benjamin Qi