Migrated from Lutece 842 天下归晋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

晋朝统一天下已有十年，曹魏、孙吴、蜀汉这些曾与天下相争的王朝，都成为了过眼云烟，仅留于故事之中。

“爷爷，讲嘛讲嘛，再讲一次赤壁之战的故事嘛！”

“你个死小子，都讲多少遍了，还听！”

“就是想听打仗嘛！”

“你小子啊...行，我就再讲一次。当时曹公率领八十万大军欲渡长江，那船队规模才叫一壮观啊，长江都铺成陆地啰。当时是这样部署的....”

曹操的船队自西向东铺于长江之上，为了方便指挥，每艘船都被赋予了相应的等级。这个等级由该船西南方船只的数量决定，即不比该船靠东并且不比该船靠北的船的数目。那是一只多么庞大的船队啊，只惜周郎一把火，樯橹灰飞烟灭......

“太刺激了，打仗好好玩啊！爷爷你怎么那么清楚当时的事儿，你的腿就是赤壁时断的吗？”

通天的火光，被激流卷去的兄弟，无数的惨叫，折断后砸向自己左腿的船柱...

看了眼激动的孙子，老者咂咂嘴，淡淡说道：“爬山采药时摔的”。

Input

第一行，一个整数$n$表示曹军船只的数量。

接下来$n$行，每行一个对整数$x_i,y_i$。表示第$i$艘船的坐标。

数据保证不会有两艘船在同一位置。

$1 \leq n \leq 100000,0 \leq x_i,y_i \leq 32000$

Output

$n$行，每行$1$个整数，分别表示从$0$级到$n - 1$级的船的数量。

行末不要有空格。

Samples

5
1 1
5 1
7 1
3 3
5 5

1
2
1
1
0

Resources

2014 UESTC Training for Data Structures