[SDOI2011]拦截导弹

某国为防御敌国的导弹袭击，研制了一套导弹拦截系统。该系统发射的第一发炮弹可以到达任意高度，也可以拦截任意速度的导弹；此后，每发炮弹的高度都不能高于前一发炮弹，其所拦截导弹的飞行速度也不能大于前一发所拦截导弹的飞行速度。

某天，雷达捕捉到敌国发射的导弹。由于该系统仍处于试用阶段，目前只有一套，因此可能无法拦截所有来袭导弹。

如果无法拦截所有导弹，则需要选择拦截数量最多的方案。这样的最优方案可能有多个；若存在多个最优方案，系统将从中随机选择一个作为最终的拦截行动方案。

我方已经获得所有敌军导弹的高度和速度。请计算最多能够拦截的导弹数量，以及在上述决策方式下，每枚导弹被拦截的概率。

输入格式

第一行包含一个正整数 $n$，表示敌军导弹的数量。

接下来 $n$ 行按照导弹的来袭顺序给出其信息。

第 $i+1$ 行包含两个正整数 $h_i$ 和 $v_i$，分别表示第 $i$ 枚导弹的高度和速度。

输出格式

输出共两行。

第一行输出一个正整数，表示最多能够拦截的导弹数量。

第二行输出 $n$ 个概率，其中第 $i$ 个数表示第 $i$ 枚导弹被拦截的概率。每个概率均须四舍五入保留小数点后 $5$ 位，不足 $5$ 位时补 $0$。

样例输入

4

3 30

4 40

6 60

3 30

样例输出

2
0.33333 0.33333 0.33333 1.00000

数据范围

• $1\le n\le 50000$；
• $1\le h_i,v_i\le 10^9$。

来源与许可

本题为 SDOI 2011 试题「拦截导弹」，题面与测试数据整理自 BZOJ。

样例 1

输入

4

3 30

4 40

6 60

3 30

输出

2
0.33333 0.33333 0.33333 1.00000