AT_code_festival_china_f Yakiniku

[problemUrl]: https://atcoder.jp/contests/code-festival-2014-china-open/tasks/code_festival_china_f

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\

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

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