题目描述

数轴上有$\red{n }$条线段，第 条线段的覆盖区间为 $\red{[l_i,r_i]}$（左右端点包含）。

求 $\red{k∈}$$\red{[l,n]，}$恰好被 $\red{k}$条线段覆盖的整数点的个数。

输入格式

第一行一个整数 $\red{n}$。

接下来 $\red{n}$行，每行两个整数 $\red{l_i,r_i}$表示第$\red{i }$条线段覆盖的区间。

输出格式

一行 $\red{n}$个整数，第 $\red{i}$个数表示恰好被 $\red{i}$条线段覆盖的整数点的个数。

样例

输入样例1

3

0 3 

1 3 

3 8

输出样例1

6 2 1

输入样例2

3

1 3 

2 4 

5 7

输出样例2

5 2 0

提示

对于$\red{30\%}$的数据满足, $\red{0<=l_i<=r_i<=10^5}$

对于$\red{100\%}$的数据满足, $\red{1<=n<=2×}$$\red{10^5,0<=l_i<=r_i<=10^{18}}$