This page is still under construction.

Parts of this page are still being built. What you see may change.

Third Round Standings

Time limit1sMemory limit32 MB

Summary
Given two rounds of scores from 0 to 650, the task asks each contestant's highest and lowest final rank over third-round scores that respect dominance.
Level

Medium7 of 10

Topics
Prefix sum, Greedy
Solved
No attempts yet

Problem

The third round of the contest is about to start. To predict the scores, assume 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 scores at least as many points as B.

In every round, including the third one, a contestant can score any integer number of points from 0 to 650. The final standings list contestants from the largest sum of the points of all three rounds to the smallest. Contestants with an equal sum get the same place, and the next contestant gets the place that counts everyone ahead. For example, contestants with sums 1000, 1000, 900, 900 and 800 get places 1, 1, 3, 3 and 5.

You know the first round score and the second round score of all NN contestants. Under the assumption above, find the highest and the lowest place each contestant can get in the final standings after all three rounds.

Input

The first line contains the number of contestants NN (1≤N≤5000001 \le N \le 500000).

Each of the next NN lines contains the first round score and the second round score of one contestant. Both scores are integers from 0 to 650.

Output

For each contestant, in the order given in the input, print two integers on one line: the highest and the lowest place that contestant can get.

Examples2

  1. Example 1

    Input
    5
250 180
250 132
220 123
132 194
220 105
    Expected output
    1 3
1 3
3 5
1 5
3 5

  2. Example 2

    Input
    10
650 550
550 554
560 512
610 460
610 456
650 392
580 436
650 366
520 456
490 456
    Expected output
    1 4
1 8
2 8
2 7
2 9
1 10
4 10
1 10
5 10
5 10