Problem Description

The cows are trying hard to invent fun new games to play. One of their current projects involves a set of $N$ intervals ($1 \le N \le 2 \cdot 10^5$), where the $i$-th interval starts at position $a_i$ on the number line and ends at position $b_i \ge a_i$. Both $a_i$ and $b_i$ are integers in the range $0 \ldots M$, where $1 \le M \le 5000$.

The game is played as follows: Bessie chooses an interval (suppose it is the $i$-th interval), and her cousin Elsie chooses an interval (suppose it is the $j$-th interval, which may be the same as Bessie's). Given a value $k$, they win if $a_i + a_j \le k \le b_i + b_j$.

For each value $k$ in the range $0 \ldots 2M$, compute the number of ordered pairs $(i, j)$ such that Bessie and Elsie can win the game.

Input Format

The first line of input contains $N$ and $M$. The next $N$ lines each describe an interval as integers $a_i$ and $b_i$.

Output Format

Output $2M+1$ lines. In order, each line should contain the answer for each $k$ in the range $0 \ldots 2M$.

2 5
1 3
2 5

0
0
1
3
4
4
4
3
3
1
1

Hint

[Sample Explanation]

In this example, for $k = 3$, there are three ordered pairs that allow Bessie and Elsie to win: $(1, 1)$, $(1, 2)$, and $(2, 1)$.

[Constraints]

• Test cases 1-2 satisfy $N \le 100, M \le 100$.
• Test cases 3-5 satisfy $N \le 5000$.
• Test cases 6-20 have no additional constraints.

Translated by ChatGPT 5