Las vacas se esfuerzan por inventar nuevos juegos interesantes. Uno de sus proyectos actuales usa un conjunto de $N$ intervalos ($1\le N\le 2\cdot 10^5$), donde el intervalo $i$ empieza en la posición $a_i$ de la recta numérica y termina en $b_i \geq a_i$. Tanto $a_i$ como $b_i$ son enteros en el rango $0 \ldots M$, donde $1 \leq M \leq 5000$.

Para jugar, Bessie elige un intervalo (digamos el $i$) y su prima Elsie elige uno (digamos el $j$, que puede ser el mismo que el de Bessie). Para un valor $k$ dado, ganan si $a_i + a_j \leq k \leq b_i + b_j$.

Para cada valor de $k$ en el rango $0 \ldots 2M$, cuenta los pares ordenados $(i,j)$ para los que Bessie y Elsie pueden ganar.

Entrada

La primera línea contiene $N$ y $M$. Cada una de las siguientes $N$ líneas describe un intervalo mediante los enteros $a_i$ y $b_i$.

Salida

Imprime $2M+1$ líneas, una para cada valor de $k$ en el rango $0 \ldots 2M$.

Ejemplos

Entrada 1

2 5
1 3
2 5

Salida 1

0
0
1
3
4
4
4
3
3
1
1

Nota

En este ejemplo, solo para $k=3$, hay tres pares ordenados que permiten ganar a Bessie y Elie: $(1, 1)$, $(1, 2)$ y $(2, 1)$.

Subtareas

• Los casos de prueba 1-2 cumplen $N\le 100, M\le 100$.

• Los casos de prueba 3-5 cumplen $N\le 5000$.

• Los casos de prueba 6-20 no tienen restricciones adicionales.

Los valores de salida pueden ser demasiado grandes para un entero de 32 bits, así que conviene usar enteros de 64 bits (por ejemplo, enteros "long long" en C o C++).

Autor del problema: Benjamin Qi