题目描述

农民约翰的奶牛们已经发现，越来越多的草沿山脊(看成是一个数轴)长的特别好。约翰有 $N$ 头牛(编号从 $1$ 到 $N$ )。每头奶牛都特别喜欢吃一定范围内的草(可能重叠)。这个范围可以看成是一个闭区间 [$S$,$E$] 。

例如两头牛 $cow_i$ 和 $cow_j$ ，它们喜欢吃草的范围分别为 [$S_i$，$E_i$] 和 [$S_j$，$E_j$] 。如果 $S_i \le S_j$ ， $E_j \le E_i$ 且 $E_i-S_i \gt E_j-S_j$ ，我们就说 $cow_i$ 比 $cow_j$ 强壮。对于每头牛来说，有多少牛是比她强呢？农民约翰需要你的帮助！

输入格式

输入文件包含多组测试数据。

每组测试数据的第一行为一个整数 $N$ ( $1 \le N \le 10^5$ ), 表示奶牛的头数；

接下来 $N$ 行，第 $i+1$ 行两个整数 $S_i$ 和 $E_i$( $0 \le S_i \lt E_i \le 10^5$ ) ，表示第 $i$ 头奶牛的范围，最后用一个 $0$ 作为文件结束。

输出格式

对于每组测试数据输出仅一行为 $n$ 个用空格分开的整数，第 $i$ 个数字表示比第 $i$ 头牛强壮的奶牛个数。

样例

3
1 2
0 3
3 4
0

1 0 0