Die Kühe arbeiten eifrig daran, interessante neue Spiele zu erfinden. Eines ihrer aktuellen Vorhaben verwendet eine Menge von $N$ Intervallen ($1\le N\le 2\cdot 10^5$). Das $i$-te Intervall beginnt auf der Zahlengeraden bei $a_i$ und endet bei $b_i \geq a_i$. Sowohl $a_i$ als auch $b_i$ sind ganze Zahlen im Bereich $0 \ldots M$, wobei $1 \leq M \leq 5000$ gilt.

Im Spiel wählt Bessie ein Intervall (etwa das $i$-te) und ihre Cousine Elsie ebenfalls eines (etwa das $j$-te, möglicherweise dasselbe wie Bessie). Für einen gegebenen Wert $k$ gewinnen sie, wenn $a_i + a_j \leq k \leq b_i + b_j$ gilt.

Zähle für jeden Wert $k$ im Bereich $0 \ldots 2M$ die geordneten Paare $(i,j)$, mit denen Bessie und Elsie gewinnen können.

Eingabe

Die erste Eingabezeile enthält $N$ und $M$. Jede der nächsten $N$ Zeilen beschreibt ein Intervall durch die ganzen Zahlen $a_i$ und $b_i$.

Ausgabe

Gib $2M+1$ Zeilen aus, eine für jeden Wert $k$ im Bereich $0 \ldots 2M$.

Beispiele

Eingabe 1

2 5
1 3
2 5

Ausgabe 1

0
0
1
3
4
4
4
3
3
1
1

Hinweis

In diesem Beispiel gibt es allein für $k=3$ drei geordnete Paare, mit denen Bessie und Elie gewinnen: $(1, 1)$, $(1, 2)$ und $(2, 1)$.

Teilaufgaben

• Die Testfälle 1-2 erfüllen $N\le 100, M\le 100$.

• Die Testfälle 3-5 erfüllen $N\le 5000$.

• Für die Testfälle 6-20 gelten keine zusätzlichen Beschränkungen.

Die Ausgabewerte können für eine 32-Bit-Ganzzahl zu groß sein. Daher solltest du gegebenenfalls 64-Bit-Ganzzahlen verwenden (etwa "long long" in C oder C++).

Autor der Aufgabe: Benjamin Qi