题目

有一道叫做“烤肉”的日本菜。这与烧烤非常相似。你在烤架上烤一些肉来做“烤肉”。

你有一个可以同时烤任意数量的肉的烤架。你想用那个烤架制作 $N$ 块“烤肉”。

“烤肉”是一道非常嫩的菜，第 $i$ 块肉必须在时间 $s_i$ 放在烤架上，并且必须在准时时间 $t_i$ 捡起来。如果你在 $t_i$ 之后捡起这块肉，那它就是“烧焦”的。如果你在 $t_i$ 之前捡起这块肉，那它就是“生”的。

然而，当你在时间 $t_i$ 捡起第 $i$ 块肉时，你完全忘记了把第 $i$ 块肉放在哪里，所以你随机从烤架上拿走 $1$ 块肉。计算每块肉被拿走时是“生”的和“烧焦”的概率。

输入

输入以以下格式给出。

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

• 第一行，一个整数 $N (1 \\leq N \\leq 100,000)$，表示你要做“烤肉”的肉块数。
• 接下来的 $N$ 行，每行两个整数 $s_i,t_i (0 \\leq s_i < t_i \\leq 10^9)$，表示你将第 $i$ 块肉放在烤架上的时间和捡起那块肉的时间。$s_1,s_2,...,s_N,t_1,t_2,...,t_N$ 互不相同。

输出

输出 $N$ 行。第 $i$ 行 $(1 \leq i \leq N)$ 包含被拿走时第 $i$ 块肉是“生”的和“烧焦”的概率，以空格分隔。如果你的答案的绝对或相对误差小于 $10^{-7}$，则被认为是正确的。

输入示例 1

2
1 3
2 4

输出示例 1

0.0 0.5
0.5 0.0

考虑第一块肉。在时间 $3$，烤架上有 $2$ 块肉。你以 $1/2$ 的概率随机拿走第二块肉，这种情况下，在时间 $4$ 时第一块肉会被捡起是“烧焦”的。

考虑第二块肉。在时间 $3$ 时，以 $1/2$ 的概率拿走第二块肉，这块肉是“生”的。

输入示例 2

5
1 2
3 4
5 10
6 9
7 8

输出示例 2

0.0000000000 0.0000000000
0.0000000000 0.0000000000
0.6666666667 0.0000000000
0.3333333333 0.3333333333
0.0000000000 0.6666666667

输入示例 3

1
0 1000000000

输出示例 3

0 0