Convoluted Intervals#11224
The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of intervals, where the -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 , where 1 \leq m \leq 5000.
To play the game, Bessie chooses some interval (say, the -th interval) and her cousin Elsie chooses some interval (say, the -th interval, possibly the same as Bessie's interval). Given some value , they win if a_i + a_j \leq k \leq b_i + b_j.
For every value of in the range , please count the number of ordered pairs for which Bessie and Elsie can win the game.
The first line contains (1 \leq n \leq 2 \cdot 10^5) and . Each of the next lines describes an interval in terms of integers a_i and b_i.
Print 2m + 1 lines as output, one for each value of in the range .
In this example, for just k = 3, there are three ordered pairs that will allow Bessie and Elsie to win: , and .
Example 1