[COCI2014-2015#3] COCI

题目描述

**译自 [COCI 2014/2015 Contest 3](http://www.hsin.hr/coci/archive/2014_2015/) T4「COCI」** 第三轮 COCI 来了!为了估分,我们猜测:如果选手 $\mathrm{A}$ 在前两轮比赛中分数都高于选手 $\mathrm{B}$,那么选手 $\mathrm{A}$ 第三轮的分数与选手 $\mathrm{B}$ 的分数**至少相等**。 在每轮比赛中(包括这一场)选手至少会为 $0$ 分,至多会得到 $650$ 分。在**总排行榜**中,选手们将会按照**三轮比赛的总得分**降序排列。如果有两名选手分数相同则排名相同,下一名分数更小的选手排名后移。 比如有 $5$ 名选手,总得分分别为 $1000,1000,900,900$ 和 $800$,那么对应的排名为 $\text{No.}\ 1,$ $\text{No.}\ 1,$ $\text{No.}\ 3,$ $\text{No.}\ 3$ 和 $\text{No.}\ 5$。 对于 $N$ 名选手中的每一名选手,我们知道他们的第一轮和第二轮得分。基于上述假设,请确定每名选手在经过三轮 COCI 之后可以获得的最高名次和最低名次。

输入输出格式

输入格式


第一行,一个整数 $N(1 \le N \le 5\times 10^5)$,表示选手的个数。 以下 $N$ 行,每行两个整数,在 $[0,650]$ 范围内,表示每个选手第一场和第二场比赛的得分。

输出格式


对于每个选手,输出一行,两个整数,分别为他可能得到的最高名次和最低名次。

输入输出样例

输入样例 #1

5
250 180
250 132
220 123
132 194
220 105

输出样例 #1

1 3
1 3
3 5
1 5
3 5

输入样例 #2

10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456

输出样例 #2

1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10

说明

$1 \le N \le 5\times 10^5$,所有的选手分数均在 $[0,650]$ 范围内。