Problem Description

Translated from T4 "COCI" of COCI 2014/2015 Contest 3.

The third round of COCI is coming! For the purpose of estimating scores, we make the following guess: if contestant $\mathrm{A}$ scored higher than contestant $\mathrm{B}$ in both of the first two rounds, then in the third round contestant $\mathrm{A}$'s score is at least equal to contestant $\mathrm{B}$'s score.

In each round (including this one), a contestant can score at least $0$ points and at most $650$ points. In the overall leaderboard, contestants are ranked in descending order by their total score over the three rounds. If two contestants have the same total score, they share the same rank, and the next contestant with a smaller score is ranked lower accordingly. For example, if there are $5$ contestants with total scores $1000, 1000, 900, 900,$ and $800$, then their ranks are $\text{No.}\ 1,$ $\text{No.}\ 1,$ $\text{No.}\ 3,$ $\text{No.}\ 3,$ and $\text{No.}\ 5$.

For each of the $N$ contestants, we know their scores in the first and second rounds. Based on the assumption above, determine the best possible rank and the worst possible rank each contestant can obtain after three rounds of COCI.

Input Format

The first line contains an integer $N \ (1 \le N \le 5\times 10^5)$, the number of contestants.

The next $N$ lines each contain two integers in the range $[0,650]$, representing the scores of each contestant in the first and second rounds.

Output Format

For each contestant, output one line with two integers: their best possible rank and their worst possible rank.

5
250 180
250 132
220 123
132 194
220 105

1 3
1 3
3 5
1 5
3 5

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

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

Hint

$1 \le N \le 5\times 10^5$. All contestants' scores are in the range $[0,650]$.

Translated by ChatGPT 5