23877번 - Convoluted Intervals 다국어

문제

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors 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 \geq a_i$. Both $a_i$ and $b_i$ are integers in the range 0ドル \ldots M,ドル where 1ドル \leq M \leq 5000$.

To play the game, Bessie chooses some interval (say, the $i$th interval) and her cousin Elsie chooses some interval (say, the $j$th interval, possibly the same as Bessie's interval). Given some value $k,ドル they win if $a_i + a_j \leq k \leq b_i + b_j$.

For every value of $k$ in the range 0ドル \ldots 2M,ドル please count the number of ordered pairs $(i,j)$ for which Bessie and Elsie can win the game.

입력

The first line of input contains $N$ and $M$. Each of the next $N$ lines describes an interval in terms of integers $a_i$ and $b_i$.

출력

Please print 2ドルM+1$ lines as output, one for each value of $k$ in the range 0ドル \ldots 2M$.

제한

힌트