Problem A
Coci
The 3rd round of COCI is already here! In order to bet on predict the scores, we have assumed the following:
-
If contestant $A$ scored strictly more points than contestant $B$ in each of the first two rounds, then in the third round $A$ will score at least an equal amount of points as $B$.
Of course, in each round (including this one, the 3rd one) it is possible to score from 0 to 650 points. On the total ranking list, contestants are sorted descending according to the sum of points from all three rounds. The contestants with an equal sum share the same place and the next contestant gets the realistic following place. For example, contestants with sums equal to 1000, 1000, 900, 900 and 800 points win places 1, 1, 3, 3 and 5, respectively.
For each of the $N$ contestants, we know the number of points scored in the first and second round. Given the aforementioned assumption, determine the highest and lowest place each contestant can get on the total ranking list after three rounds of COCI.
Input
The first line of input contains an integer $N$ ($1 \leq N \leq 500\, 000$), the number of contestants.
Each of the following $N$ lines contains two integers from the interval $[0, 650]$: the number of points each contestant won in the first and second round.
Output
For each contestant, in the order given in the input, output two integers per line: the required highest and lowest place they can get on the total ranking list.
Sample Input 1 | Sample Output 1 |
---|---|
5 250 180 250 132 220 123 132 194 220 105 |
1 3 1 3 3 5 1 5 3 5 |
Sample Input 2 | Sample Output 2 |
---|---|
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 |