COCI 的第三轮比赛已经到来！为了预测成绩，我们做出了以下假设：

• 如果选手 A 在前两轮的每一轮中得分都严格大于选手 B，那么在第三轮中，A 的得分将大于或等于 B 的得分。

当然，在每一轮（包括第三轮）中，选手的得分都在 $0$ 到 $650$ 分之间。在总排名表中，选手按照三轮总得分从大到小进行排序。总得分相同的选手并列同一名次，而紧随其后的选手的名次为实际的排名。例如，总得分分别为 $1000$、$1000$、$900$、$900$ 和 $800$ 分的选手，其名次分别为第 $1$、第 $1$、第 $3$、第 $3$ 和第 $5$ 名。

对于 $N$ 名选手中的每一位，我们已知其在第一轮和第二轮中的得分。在上述假设下，请确定每位选手在 COCI 三轮结束后的总排名表中，可能获得的最高排名和最低排名。

输入格式

输入第一行包含一个整数 $N$ ($1 \le N \le 500\,000$)，表示选手人数。

接下来的 $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