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 $NN$ intervals ($1\le N\le 2\cdot {10}^{5}1\backslash le\; N\backslash le\; 2\backslash cdot\; 10^5$), where the $ii$th interval starts at position $a_{i}a\_i$ on the number line and ends at position $b_i\ge a_{i}b\_i\; \backslash geq\; a\_i$. Both $a_{i}a\_i$ and $b_{i}b\_i$ are integers in the range $0\dots M0\; \backslash ldots\; M$, where $1\le M\le 50001\; \backslash leq\; M\; \backslash leq\; 5000$.

To play the game, Bessie chooses some interval (say, the $ii$th interval) and her cousin Elsie chooses some interval (say, the $jj$th interval, possibly the same as Bessie's interval). Given some value $kk$, they win if $a_i+a_j\le k\le b_i+b_{j}a\_i\; +\; a\_j\; \backslash leq\; k\; \backslash leq\; b\_i\; +\; b\_j$.

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

입력

The first line of input contains $NN$ and $MM$. Each of the next $NN$ lines describes an interval in terms of integers $a_{i}a\_i$ and $b_{i}b\_i$.

출력

Please print $2M+12M+1$ lines as output, one for each value of $kk$ in the range $0\dots 2M0\; \backslash ldots\; 2M$.

2 5
1 3
2 5

0
0
1
3
4
4
4
3
3
1
1