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, where the i-th interval starts at position a[i] on the number line and ends at position b[i] ≥ a[i]. Both a[i] and b[i] are integers in the range 0..m, where 1 ≤ m ≤ 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] ≤ k ≤ b[i] + b[j].
For every value of k in the range 0..2m, please count the number of ordered pairs (i, j) for which Bessie and Elsie can win the game.
Input
The first line contains n (1 ≤ n ≤ 2 * 10^5) and m. Each of the next n lines describes an interval in terms of integers a[i] and b[i].
Output
Print 2m + 1 lines as output, one for each value of k in the range 0..2m.
Example
In this example, for just k = 3, there are three ordered pairs that will allow Bessie and Elie to win: (1, 1), (1, 2) and (2, 1).