Коровы усердно придумывают новые интересные игры. В одном из их нынешних проектов используется набор из $N$ интервалов ($1\le N\le 2\cdot 10^5$), где $i$-й интервал начинается в точке $a_i$ числовой прямой и заканчивается в точке $b_i \geq a_i$. И $a_i$, и $b_i$ — целые числа из диапазона $0 \ldots M$, где $1 \leq M \leq 5000$.

В игре Bessie выбирает некоторый интервал (скажем, $i$-й), а её кузина Elsie выбирает некоторый интервал (скажем, $j$-й, возможно, тот же, что и Bessie). Для заданного значения $k$ они выигрывают, если $a_i + a_j \leq k \leq b_i + b_j$.

Для каждого значения $k$ в диапазоне $0 \ldots 2M$ посчитайте число упорядоченных пар $(i,j)$, при которых Bessie и Elsie могут выиграть.

Входные данные

Первая строка входных данных содержит $N$ и $M$. Каждая из следующих $N$ строк описывает интервал целыми числами $a_i$ и $b_i$.

Выходные данные

Выведите $2M+1$ строк, по одной для каждого значения $k$ в диапазоне $0 \ldots 2M$.

Примеры

Входные данные 1

2 5
1 3
2 5

Выходные данные 1

0
0
1
3
4
4
4
3
3
1
1

Примечание

В этом примере только для $k=3$ есть три упорядоченные пары, позволяющие Bessie и Elie выиграть: $(1, 1)$, $(1, 2)$ и $(2, 1)$.

Подзадачи

• В тестах 1-2 выполняется $N\le 100, M\le 100$.

• В тестах 3-5 выполняется $N\le 5000$.

• В тестах 6-20 нет дополнительных ограничений.

Выходные значения могут быть слишком велики для 32-битного целого числа, поэтому стоит использовать 64-битные целые числа (например, "long long" в C или C++).

Автор задачи: Benjamin Qi