Le mucche si impegnano a inventare nuovi giochi interessanti. Uno dei loro progetti attuali usa un insieme di $N$ intervalli ($1\le N\le 2\cdot 10^5$), in cui l’intervallo $i$ inizia nella posizione $a_i$ della retta numerica e termina in $b_i \geq a_i$. Sia $a_i$ sia $b_i$ sono interi nell’intervallo $0 \ldots M$, dove $1 \leq M \leq 5000$.

Per giocare, Bessie sceglie un intervallo (ad esempio l’intervallo $i$) e sua cugina Elsie ne sceglie uno (ad esempio l’intervallo $j$, che può essere lo stesso di Bessie). Dato un valore $k$, vincono se $a_i + a_j \leq k \leq b_i + b_j$.

Per ogni valore $k$ nell’intervallo $0 \ldots 2M$, conta le coppie ordinate $(i,j)$ con cui Bessie ed Elsie possono vincere.

Input

La prima riga contiene $N$ e $M$. Ognuna delle successive $N$ righe descrive un intervallo tramite gli interi $a_i$ e $b_i$.

Output

Stampa $2M+1$ righe, una per ogni valore $k$ nell’intervallo $0 \ldots 2M$.

Esempi

Input 1

2 5
1 3
2 5

Output 1

0
0
1
3
4
4
4
3
3
1
1

Nota

In questo esempio, per il solo $k=3$, tre coppie ordinate consentono a Bessie ed Elie di vincere: $(1, 1)$, $(1, 2)$ e $(2, 1)$.

Sottoproblemi

• I test 1-2 soddisfano $N\le 100, M\le 100$.

• I test 3-5 soddisfano $N\le 5000$.

• I test 6-20 non hanno vincoli aggiuntivi.

I valori di output possono essere troppo grandi per un intero a 32 bit, quindi può essere opportuno usare interi a 64 bit (ad esempio gli interi "long long" in C o C++).

Autore del problema: Benjamin Qi