Magic

A group of $n$ wizards must join forces to fight the forces of evil. The $i^{th}$ wizard resides on the real line at coordinate $x_i$ and has $e_i$ units of experience accumulated from their previous "mathemagical" encounters. The coordinates of the wizards are pairwise distinct.

To join forces, wizards must share their experience with each other: the $i^{th}$ wizard will choose another wizard $j \neq i$ as their mentor. If the $i^{th}$ wizard chooses the $j^{th}$ mentor, the $i^{th}$ wizard will gain $\frac{e_j}{\vert x_j - x_i \vert}$ units of experience in the process. Note that wizards cannot choose to mentor themselves. Compute for each wizard the maximum experience they can gain by choosing the best mentor for themselves. Note that a wizard can be a mentor for multiple other wizards.

Input

The first line contains the number of wizards $n$.

Each of the following $n$ lines contains a pair of two integers. The $i^{th}$ of these lines contains the coordinate and the experience of the $i^{th}$ wizard: $x_i$ and $e_i$.

Output

The output contains $n$ lines, one line for each wizard. The $i^{th}$ line represents the maximum possible experience hain for the $i^{th}$ wizard. The experience gain is represented by two integers $p$ and $q$ such that $\frac{p}{q}$ is the answer written as an irreductible fraction.

Constraints

• $2 \leq n \leq 2 \cdot 10^5$
• $1 \leq x_i, e_i \leq 10^9$
• $x_1 < x_2 < \dots < x_n$

Subtasks

Example

stdin

4
1 2
2 1
4 3
6 2

stdout

1 1
2 1
1 1
3 2

Explanation

The first wizard is mentored by the third wizard. The experience gained is $\frac{3}{4 - 1} = \frac{1}{1}$.

The second wizard is mentored by the first wizard. The experience gained is $\frac{2}{2 - 1} = \frac{2}{1}$.

The third wizard is mentored by the fourth wizard. The experience gained is $\frac{2}{6 - 4} = \frac{1}{1}$

The fourth wizard is mentored by the third wizard. The experience gained is $\frac{3}{6 - 4} = \frac{3}{2}$.