背景

译自 Northwestern Europe Regional Contest (NWERC) 2022 Problem J。

原题许可协议为 CC BY-SA。

题目描述

你终于成功做出了终极 stroopwafel，上面的正方形数量刚刚好。辛苦完成后，你把 stroopwafel 暂时留在原地几秒钟，去给自己拿一杯热饮。你满怀期待地回来，准备享用这份美味，却发现 stroopwafel 不见了！尽管你只离开了很短时间，还是有人趁机偷走了它。

你查看了监控录像，看到共有 $n$ 名嫌疑人曾经进入过你放置 stroopwafel 的房间，每个人都恰好进入并离开一次。看到这些之后，你已经大致知道是谁拿走了它，因为你的宿敌 Rob——他在抢劫方面有些背景——也在嫌疑人之中。但你决定给他一个无罪的机会，于是审问了每一名嫌疑人。

不出所料，每个嫌疑人都声称自己无罪。不过，一些嫌疑人还为其他嫌疑人提供了不在场证明。具体来说，当且仅当嫌疑人 $A$ 在嫌疑人 $B$ 待在房间的整个时间段内也一直在房间里时，$A$ 为 $B$ 提供不在场证明。

你认为，如果某个嫌疑人的不在场证明来自一个本身也有说服力的嫌疑人，那么这个嫌疑人会更有说服力。形式化地，没有不在场证明的嫌疑人的说服力为 $0$。否则，他们的说服力等于为他们提供不在场证明的嫌疑人中，说服力最大的那一位的说服力再加 $1$。你的任务是计算每个嫌疑人的说服力。

输入格式

输入包含：

• 一行一个整数 $n$（$1 \leq n \leq 2\cdot 10^5$），表示嫌疑人数。
• 接下来 $n$ 行，每行两个整数 $a$ 和 $t$（$1 \leq a,t \leq 10^9$），分别表示某个嫌疑人到达的时刻以及停留的时长。

保证不存在两个到达时刻相同且停留时长也相同的嫌疑人。

输出格式

输出每个嫌疑人的说服力。

4
2 8
1 7
4 5
5 2

0 0 1 2 

5
2 4
3 3
2 2
4 2
4 1

0 1 1 2 3 

提示

【数据规模与约定】

对于所有数据，满足 $1 \leq n \leq 2\cdot 10^5$；$1 \leq a,t \leq 10^9$；不存在两个到达时刻相同且停留时长也相同的嫌疑人。