Krowy pracują nad wymyślaniem ciekawych nowych gier. Jeden z ich obecnych projektów wykorzystuje zbiór $N$ przedziałów ($1\le N\le 2\cdot 10^5$), gdzie $i$-ty przedział zaczyna się w punkcie $a_i$ osi liczbowej i kończy w punkcie $b_i \geq a_i$. Zarówno $a_i$, jak i $b_i$ są liczbami całkowitymi z zakresu $0 \ldots M$, gdzie $1 \leq M \leq 5000$.

W grze Bessie wybiera przedział (na przykład $i$-ty), a jej kuzynka Elsie wybiera przedział (na przykład $j$-ty, być może ten sam co Bessie). Dla danej wartości $k$ wygrywają, jeśli $a_i + a_j \leq k \leq b_i + b_j$.

Dla każdej wartości $k$ z zakresu $0 \ldots 2M$ policz uporządkowane pary $(i,j)$, dla których Bessie i Elsie mogą wygrać.

Wejście

Pierwszy wiersz wejścia zawiera $N$ i $M$. Każdy z następnych $N$ wierszy opisuje przedział za pomocą liczb całkowitych $a_i$ i $b_i$.

Wyjście

Wypisz $2M+1$ wierszy, po jednym dla każdej wartości $k$ z zakresu $0 \ldots 2M$.

Przykład

Wejście 1

2 5
1 3
2 5

Wyjście 1

0
0
1
3
4
4
4
3
3
1
1

Uwagi

W tym przykładzie tylko dla $k=3$ są trzy uporządkowane pary pozwalające Bessie i Elie wygrać: $(1, 1)$, $(1, 2)$ oraz $(2, 1)$.

Podzadania

• Testy 1-2 spełniają $N\le 100, M\le 100$.

• Testy 3-5 spełniają $N\le 5000$.

• Testy 6-20 nie mają dodatkowych ograniczeń.

Wartości wyjściowe mogą być zbyt duże dla 32-bitowej liczby całkowitej, więc warto użyć 64-bitowych liczb całkowitych (na przykład typu "long long" w C lub C++).

Autor zadania: Benjamin Qi