Determining Possible Final Rankings in COCI

In the third round of COCI, there is an interesting assumption based on the scores from the first two rounds. Suppose there are (N) contestants. For each contestant (i), you are given two scores (a_i) and (b_i) from rounds 1 and 2 respectively. In the third round, each contestant can score an integer number of points (x_i) such that [ 0 \le x_i \le 650. ] However, there is a twist. It is assumed that if contestant (i) scored strictly higher than contestant (j) in both the first round and the second round (i.e. (a_i > a_j) and (b_i > b_j)), then contestant (i)’s third round score must be at least as high as that of contestant (j); in other words, (x_i \ge x_j).

The final total score of a contestant is defined as: [ total_i = a_i + b_i + x_i. ] During the ranking procedure the contestants are sorted in descending order of their total scores. If two or more contestants have the same total score, they share the same rank. More precisely, the rank of a contestant is (1+) (number of contestants with a strictly higher total score). For example, if 5 contestants have total scores: 1000, 1000, 900, 900, 800, their ranks will be No. 1, No. 1, No. 3, No. 3, and No. 5 respectively.

Assuming that the unknown third round scores can be assigned arbitrarily as long as the above constraints are satisfied, determine for each contestant the best (smallest) possible rank and the worst (largest) possible rank they can achieve after the third round.

How to approach the problem?

For each contestant (i) let [ fixed_i = a_i + b_i. ]
Best Case:
Assign contestant (i) the maximum third round score, i.e. (x_i = 650), so that his best total is (fixed_i+650). For every other contestant (j) you want their total to be as low as possible, so assign (x_j = 0) (this is valid by the constraints, because setting everyone else to 0 trivially satisfies (x_i \ge x_j) when necessary). Then the best rank for contestant (i) is [ 1+;#{j\neq i \mid fixed_j > fixed_i+650}. ]
Worst Case:
Assign contestant (i) the minimum third round score, i.e. (x_i = 0). For every other contestant (j), you want their total to be as high as possible, i.e. set (x_j = 650). However, if contestant (i) has dominated contestant (j) in the first two rounds (i.e. (a_i > a_j) and (b_i > b_j)), then by the constraint we must have (x_j \le x_i = 0), so in that case the best we can do for (j) is (x_j = 0).

Thus, for each contestant (j) ( (j \neq i) ) in the worst case we have a maximum possible total of: [ \text{total}_j = \begin{cases} fixed_j, & \text{if } a_i > a_j \text{ and } b_i > b_j,\[8pt] fixed_j + 650, & \text{otherwise.} \end{cases} ] And the worst rank for contestant (i) becomes: [ 1+;#{j\neq i \mid \text{total}_j > fixed_i}. ]

Your task is to compute, for every contestant, these best and worst ranks.

Input Format:

• The first line contains an integer \(N\) (number of contestants).
• Each of the following \(N\) lines contains two integers \(a_i\) and \(b_i\) (the scores from rounds 1 and 2 respectively).

Output Format:

• Output \(N\) lines. The \(i\)-th line should contain two integers: the best rank and the worst rank for contestant \(i\), separated by a space.

Constraints:

• \(0 \le a_i, b_i \le 650\)
• \(1 \le N \le 10^5\) (for example)

inputFormat

The first line contains an integer N. The following N lines each contain two space-separated integers a_i and b_i.

outputFormat

Output N lines. The i-th line must contain two space-separated integers: the best and worst possible ranks of contestant i.

sample

3
300 300
200 200
100 100

1 1
1 2
1 3

</p>