Les vaches s’efforcent d’inventer de nouveaux jeux intéressants. L’un de leurs projets actuels utilise un ensemble de $N$ intervalles ($1\le N\le 2\cdot 10^5$), où le $i$-ème intervalle commence en $a_i$ sur la droite numérique et se termine en $b_i \geq a_i$. Les valeurs $a_i$ et $b_i$ sont des entiers de l’intervalle $0 \ldots M$, où $1 \leq M \leq 5000$.

Pour jouer, Bessie choisit un intervalle (disons le $i$-ème) et sa cousine Elsie en choisit un (disons le $j$-ème, éventuellement le même que Bessie). Pour une valeur $k$ donnée, elles gagnent si $a_i + a_j \leq k \leq b_i + b_j$.

Pour chaque valeur de $k$ dans l’intervalle $0 \ldots 2M$, comptez les couples ordonnés $(i,j)$ pour lesquels Bessie et Elsie peuvent gagner.

Entrée

La première ligne contient $N$ et $M$. Chacune des $N$ lignes suivantes décrit un intervalle par les entiers $a_i$ et $b_i$.

Sortie

Affichez $2M+1$ lignes, une pour chaque valeur de $k$ dans l’intervalle $0 \ldots 2M$.

Exemples

Entrée 1

2 5
1 3
2 5

Sortie 1

0
0
1
3
4
4
4
3
3
1
1

Remarque

Dans cet exemple, pour $k=3$ seulement, trois couples ordonnés permettent à Bessie et Elie de gagner : $(1, 1)$, $(1, 2)$ et $(2, 1)$.

Sous-tâches

• Les cas de test 1-2 vérifient $N\le 100, M\le 100$.

• Les cas de test 3-5 vérifient $N\le 5000$.

• Les cas de test 6-20 ne sont soumis à aucune contrainte supplémentaire.

Les valeurs de sortie peuvent dépasser la capacité d’un entier sur 32 bits ; vous pouvez donc utiliser des entiers sur 64 bits (par exemple les entiers "long long" en C ou C++).

Auteur du problème : Benjamin Qi