题目描述

$n$ 名选手正在参加一个神秘比赛，比赛按照名次发放奖金。比赛中有两道程序设计题目，每道题目的满分为 $10^4$ 分，在比赛结束时，可以从榜单上看到每位选手的得分情况，第 $i$ 位选手的两道题目的得分分别为 $a_{i,1}, a_{i,2}$。虽然比赛已经结束，但排名却并非最终确定，因为这个比赛为每道题目都设置了最终测试，如果没有通过最终测试，得分将会归 $0$。具体来说，如果第 $i$ 位选手通过了第 $j$ 道题目的最终测试，则他该题的得分为 $a_{i,j}$，否则，他该题的得分为 $0$。

通过占卜大法，你获知每个人每道题目都独立地有 $50\%$ 的概率能通过最终测试，有 $50\%$ 不能通过。现在你想要知道，每一位选手的期望的排名是多少。

排名的定义为，假设有 $r$ 名选手最终的总分数高于第 $i$ 名选手最终的总分数，则第 $i$ 名选手的排名为 $r+1$，比如 $4$ 位选手的最终总分数分别为 $5000,15000,20000,15000$，则他们的排名分别是 $4,2,1,2$。

输入格式

第一行，一个正整数 $n$，表示选手数。

接下来 $n$ 行，第 $i$ 行有两个整数 $a_{i,1}, a_{i,2}$，以空格相隔。

输出格式

输出 $n$ 行，第 $i$ 行为一个小数，表示第 $i$ 位选手的期望排名。输出答案与标准答案的绝对误差或相对误差小于 $10^{−6}$ 算正确。

样例

2
10000 10000
10000 5000

1.3125
1.5

经过简单计算可以得到：

第 $1$ 位选手得第 $1$ 名的概率为 $\frac {11}{16}$，得第 $2$ 名的概率为 $\frac {5}{16}$，因此他的排名的期望为 $\frac{11}{16}+2\times \frac{5}{16}=\frac{21}{16}=1.3125$。

第 $2$ 位选手的第 $1$ 名的概率为 $\frac 1 2$，得第 $2$ 名的概率为 $\frac 1 2$，因此他的排名的期望为 $\frac 1 2+2\times \frac 1 2=\frac{3}{2}=1.5$。

10
10000 7000
3000 8000
3000 10000
6000 4000
2000 8000
4000 1000
9000 9000
8000 10000
3000 6000
3000 7000

4.0
5.125
4.5
5.375
5.4375
7.0
3.9375
3.6875
5.875
5.375

数据范围

• 对于 $30\%$ 数据，满足 $1 \le n \le 10$。
• 对于 $60\%$ 数据，满足 $1 \le n \le 10^3$。
• 对于 $100\%$ 数据，满足 $1 \le n \le 10^5$，$0\le a_{i,j}\le 10^4$。