As vacas estão empenhadas em inventar novos jogos interessantes. Um dos projetos atuais envolve um conjunto de $N$ intervalos ($1\le N\le 2\cdot 10^5$), em que o intervalo $i$ começa na posição $a_i$ da reta numérica e termina em $b_i \geq a_i$. Tanto $a_i$ quanto $b_i$ são inteiros no intervalo $0 \ldots M$, onde $1 \leq M \leq 5000$.

Para jogar, Bessie escolhe um intervalo (digamos, o $i$) e sua prima Elsie escolhe um intervalo (digamos, o $j$, possivelmente o mesmo que Bessie). Para um valor $k$ dado, elas vencem se $a_i + a_j \leq k \leq b_i + b_j$.

Para cada valor de $k$ no intervalo $0 \ldots 2M$, conte os pares ordenados $(i,j)$ em que Bessie e Elsie podem vencer.

Entrada

A primeira linha contém $N$ e $M$. Cada uma das próximas $N$ linhas descreve um intervalo pelos inteiros $a_i$ e $b_i$.

Saída

Imprima $2M+1$ linhas, uma para cada valor de $k$ no intervalo $0 \ldots 2M$.

Exemplos

Entrada 1

2 5
1 3
2 5

Saída 1

0
0
1
3
4
4
4
3
3
1
1

Nota

Neste exemplo, somente para $k=3$, existem três pares ordenados que permitem a Bessie e Elie vencer: $(1, 1)$, $(1, 2)$ e $(2, 1)$.

Subtarefas

• Os casos de teste 1-2 satisfazem $N\le 100, M\le 100$.

• Os casos de teste 3-5 satisfazem $N\le 5000$.

• Os casos de teste 6-20 não têm restrições adicionais.

Os valores de saída podem ser grandes demais para um inteiro de 32 bits, então convém usar inteiros de 64 bits (por exemplo, inteiros "long long" em C ou C++).

Autor do problema: Benjamin Qi