COCI '14 Contest 3 #4 Coci

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M
Problem type

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 \le N \le 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

5
250 180
250 132
220 123
132 194
220 105

Sample Output 1

1 3
1 3
3 5
1 5
3 5

Sample Input 2

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

Sample Output 2

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

Comments