Problem Description

Input Format

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 Format

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} $.

Sample Input and Output

Sample Input #1

2
1 3
2 4

Sample Output #1

0.0 0.5
0.5 0.0

Sample Input #2

5
1 2
3 4
5 10
6 9
7 8

Sample Output #2

0.0000000000 0.0000000000
0.0000000000 0.0000000000
0.6666666667 0.0000000000
0.3333333333 0.3333333333
0.0000000000 0.6666666667

Sample Input #3

1
0 1000000000

Sample Output #3

0 0

Notes/Hints

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'.

Sample Explanation 1

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 部分

见题面 Output 部分