F - Yakiniku Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

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 1st piece of meat. At the time 3 there are 2 pieces of meat on the grill. You pick the 2nd piece of meat with probability 1/2 and in that case at the time 4 the 1st meat will be picked up 'scorched'.

Think of the 2nd piece of meat. At the time 3 the 2nd 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