奶牛们正在努力发明有趣的新游戏。她们目前的一个项目涉及一组 $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

2 5
1 3
2 5

输出格式 1

0
0
1
3
4
4
4
3
3
1
1

说明

在这个样例中，仅考虑 $k=3$，有三个能让 Bessie 和 Elie 获胜的有序对：$(1, 1)$、$(1, 2)$ 和 $(2, 1)$。

子任务

• 测试点 1-2 满足 $N\le 100, M\le 100$。

• 测试点 3-5 满足 $N\le 5000$。

• 测试点 6-20 没有额外限制。

注意，输出的数值可能超过 32 位整数的范围，因此你可能需要使用 64 位整数（例如 C 或 C++ 中的 "long long" 整数）。

题目作者：Benjamin Qi