题目描述

农夫约翰的奶牛们发现，沿着山脊（可以看作一条一维数轴）生长的三叶草特别美味。

农夫约翰共有N头奶牛（编号从1到N）。每头奶牛都有一个特别喜欢的区间[S,E]，这些区间可能会重叠。

奶牛之间存在强弱关系。对于两头奶牛i和j，如果满足以下三个条件，则称奶牛i比奶牛j强： $1. Si ≤ Sj$ $2. Ej ≤ Ei$ $3. Ei - Si > Ej - Sj$

对于每头奶牛，需要计算有多少头奶牛比它强。农夫约翰需要你的帮助！

输入格式

输入包含多个测试用例。

每个测试用例的第一行是一个整数$N（1 ≤ N ≤ 10^5）$，表示奶牛的数量。接下来的N行，每行包含两个整数$S和E（0 ≤ S < E ≤ 10^5）$，分别表示某头奶牛喜欢的区间起点和终点。位置是相对于山脊起点的距离。

输入以一个单独的0结束。

输出格式

对于每个测试用例，输出一行，包含$N$个用空格分隔的整数，第i个整数表示比第i头奶牛强的奶牛数量。

输入样例1

3
1 2
0 3
3 4
0

输出样例1

1 0 0

提示

输入输出数据量较大，建议使用scanf和printf。

来源

POJ竞赛，作者：Mathematica@ZSU