# [USACO21DEC] Convoluted Intervals S
## 题目描述
奶牛们正在努力尝试发明有趣的新游戏来玩。他们目前的工作之一与一组 $N$ 个区间（$1\le N\le 2\cdot 10^5$）有关，其中第 $i$ 个区间从数轴上的 $a_i$ 位置开始，并在位置 $b_i \geq a_i$ 结束。$a_i$ 和 $b_i$ 均为 $0 \ldots M$ 范围内的整数，其中 $1 \leq M \leq 5000$。
这个游戏的玩法是，Bessie 选择某个区间（假设是第 $i$ 个区间），而她的表妹 Elsie 选择某个区间（假设是第 $j$ 个区间，可能与 Bessie 所选的的区间相同）。给定某个值 $k$，如果 $a_i + a_j \leq k \leq b_i + b_j$，则她们获胜。
对范围 $0 \ldots 2M$ 内的每个值 $k$，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 $(i,j)$ 的数量。
## 输入格式
输入的第一行包含 $N$ 和 $M$。以下 $N$ 行每行以整数 $a_i$ 和 $b_i$ 的形式描述一个区间。
## 输出格式
输出 $2M+1$ 行，依次包含范围 $0 \ldots 2M$ 中的每一个 $k$ 的答案。
## 样例 #1
### 样例输入 #1
```
2 5
1 3
2 5
```
### 样例输出 #1
```
0
0
1
3
4
4
4
3
3
1
1
```
## 提示
【样例解释】
在这个例子中，对于 $k=3$，有三个有序对可以使得 Bessie 和 Elsie 获胜：$(1, 1)$，$(1, 2)$，和 $(2, 1)$。
【数据范围】
- 测试点 1-2 满足 $N\le 100, M\le 100$。
- 测试点 3-5 满足 $N\le 5000$。
- 测试点 6-20 没有额外限制。
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≤N≤2⋅10
5), where the i
th interval starts at position ai
on the number line and ends at position bi≥ai
. Both ai
and bi
are integers in the range 0…M
, where 1≤M≤50001≤M≤5000
.
To play the game, Bessie chooses some interval (say, the ith interval) and her cousin Elsie chooses some interval (say, the jth interval, possibly the same as Bessie's interval). Given some value k, they win if ai+aj≤k≤bi+bj.
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.