奶牛们正在努力尝试发明有趣的新游戏来玩。

他们目前的工作之一与一组 $N$ 个区间有关，其中第 $i$ 个区间从数轴上的 $a_i$ 位置开始，并在位置 $b_i$ 结束。

$a_i$ 和 $b_i$ 均为 $0 \dots M$ 范围内的整数，其中 $1≤M≤5000$。

这个游戏的玩法是，Bessie 选择某个区间（假设是第 $i$ 个区间），而她的表妹 Elsie 选择某个区间（假设是第 $j$ 个区间，可能与 Bessie 所选的的区间相同）。

给定某个值 $k$，如果 $a_i+a_j \leq k \leq b_i+b_j$，则她们获胜。

对范围 $0 \dots 2*M$ 内的每个值 $k$，请计算使得 Bessie 和 Elsie 可以赢得游戏的有序对 $(i,j)$ 的数量。

输入格式

输入的第一行包含 $N$ 和 $M$。

以下 $N$ 行每行以整数 $a_i$ 和 $b_i$ 的形式描述一个区间。

输出格式

输出 $2*M+1$ 行，依次包含范围 $0…2*M$ 中的每一个 $K$ 的答案。

2 5
1 3
2 5

0
0
1
3
4
4
4
3
3
1
1

提示

$1≤N≤2×10^5$,
$1≤M≤5000$,
$a_i+a_j \leq k \leq b_i+b_j$。

样例解释

在这个例子中，对于 $k=3$，有三个有序对可以使得 Bessie 和 Elsie 获胜：(1,1)，(1,2)，和 (2,1)。