You are given n segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every k∈[1…n], calculate the number of points with integer coordinates such that the number of segments that cover these points equals k. A segment with endpoints li and ri covers point x if and only if li≤x≤ri.

Input
The first line of the input contains one integer n (1≤n≤2⋅105) — the number of segments.

The next n lines contain segments. The i-th line contains a pair of integers li,ri (0≤li≤ri≤1018) — the endpoints of the i-th segment.

Output
Print n space separated integers cnt1,cnt2,…,cntn, where cnti is equal to the number of points such that the number of segments that cover these points equals to i.

Examples
Input
3
0 3
1 3
3 8
Output
6 2 1
Input
3
1 3
2 4
5 7
Output
5 2 0

题目大致意思是给定n条线段，分别输出被覆盖1次~n次的点的数量。
解题报告：我好久没写博客了，其实这道题看了题解也是模棱两可，，主要他这道题l,r范围太大了，如果o n的做法扫描一遍那肯定会T，主要会浪费在那些没被覆盖的点上面，可以用个map来存左端点，还有右端点，利用差分的思想，开创一个答案数组，记录被覆盖i次的数量，用map的迭代器遍历每个点，注意map的it.second是不行的,要用it->second

#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
const	int N=200010;
map<ll,int> mp;
int d[N];
ll ans1[N];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		ll l,r;
		cin>>l>>r;
		mp[l]++;
		mp[r+1]--;
	}
	int cnt=0;
	ll last=0;
	int ans=0;
	for(map<ll,int>::iterator it =mp.begin();it!=mp.end();it++)
	{
		if(it==mp.begin())
		{
			ans+=it->second;
			last=it->first;
			continue;
		}
		ans1[ans]+=(it->first-last);
		ans+=it->second;
		last=it->first;
	}
	for(int i=1;i<=n;i++)
	cout<<ans1[i]<<' ';
	cout<<endl;
}