Problem

There's a Japanese dish called 'Yakiniku', which is very similar to barbecue. You roast some pieces of meat on a grill to cook 'Yakiniku'.

You have a grill that can roast any number of pieces of meat on it at once. You want to make $N$ pieces of 'Yakiniku' using that grill.

'Yakiniku' is a very tender dish that the $i$-th piece of meat must be put on the grill at the time $s_i$, and must be picked up at the time $t_i$ sharp. If you pick the piece of meat later than $t_i$ that piece is 'scorched'. If you pick the piece of meat earlier than $t_i$ that piece is 'underdone'.

However, when you pick the $i$-th piece of meat at the time $t_i$, you totally forget where you put the $i$-th piece of meat on, so you pick $1$ piece of meat from the grill at random. Calculate the probability of each piece of meat picked up 'underdone' and 'scorched'.

Input

Input is given in the following format.

$N$ $s_1$ $t_1$ $s_2$ $t_2$ : $s_N$ $t_N$

• On the first line, you will be given the integer $N (1 \\leq N \\leq 100,000)$, the number of pieces of meat you are going to cook 'Yakiniku'.
• Following $N$ lines consists of two integers $s_i,t_i (0 \\leq s_i < t_i \\leq 10^9)$, the time you put the $i$-th meat on the grill and the time you have to pick up that meat from the grill. $s_1,s_2,...,s_N,t_1,t_2,...,t_N$ are distinct from each other.

Output

Output $N$ lines. The $i$-th $(1 \\leq i \\leq N)$ line should contain the probability of $i$-th piece of meat picked up from the grill 'underdone' and 'scorched' separated by space. Your answer is considered correct if it has an absolute or relative error less than $10^{-7}$.

Input Example 1

2
1 3
2 4

Output Example 1

0.0 0.5
0.5 0.0

Think of the $1$st piece of meat. At the time $3$ there are $2$ pieces of meat on the grill. You pick the $2$nd piece of meat with probability $1/2$ and in that case at the time $4$ the $1$st meat will be picked up 'scorched'.

Think of the $2$nd piece of meat. At the time $3$ the $2$nd piece of meat is taken from the grill with probability $1/2$ and is 'underdone'.

Input Example 2

5
1 2
3 4
5 10
6 9
7 8

Output Example 2

0.0000000000 0.0000000000
0.0000000000 0.0000000000
0.6666666667 0.0000000000
0.3333333333 0.3333333333
0.0000000000 0.6666666667

Input Example 3

1
0 1000000000

Output Example 3

0 0