#628. 奶牛的势力范围

奶牛的势力范围

题目描述

平面直角坐标系中有 NN 头奶牛,奶牛的位置两两不同。每头奶牛的势力范围为其左下方区域,即对于奶牛 i:(Xi,Yi)i: (X_i, Y_i) 来说,如果另一头奶牛 j:(Xj,Yj)j: (X_j, Y_j) 满足 Xj≤XiX_j ≤ X_i 且 Yj≤YiY_j ≤ Y_i ,则称奶牛 ii 统领着奶牛 jj 。如果奶牛 ii 统领着 kk 头奶牛,则称奶牛 ii 为 kk 级奶牛。

问:各级奶牛的数量分别有多少?

输入格式

第一行:一个整数 NN,表示奶牛的数量;

接下来 N 行:每行两个整数 Xi,YiX_i, Y_i 表示奶牛 ii 的坐标。数据保证奶牛的位置两两不同。

输出格式

共 NN 行,每行一个整数,其中第 ii 行的整数表示 i−1i-1 级奶牛的数量。

样例输入

5
1 1
2 1
2 2
4 1
3 3

样例输出

1
1
2
1
0

数据范围与提示

100% 的数据:1≤N≤2×104,0≤Xi,Yi≤4×1041 ≤ N ≤ 2 × 10^4, 0 ≤ X_i, Y_i ≤ 4 × 10^4。