Missile Interception Probability

A certain country has developed a missile interception system to defend against enemy missile attacks. However, the system has a defect: although its first interceptor shell can be fired to any height and intercept a missile of any speed, every subsequent shell must not exceed the height of the previous one and the intercepted missile’s speed must not exceed that of the previous intercepted missile.

On one day, enemy missiles are launched. Since the system is still in the testing phase there is only one set, and it may be impossible to intercept all missiles. Therefore, the decision is made to choose a scheme that intercepts the maximum number of missiles (i.e. minimizes national losses). It turns out that there may be several optimal schemes. In case of multiple optimal solutions, one of them is selected uniformly at random as the final operational blueprint.

Your intelligence has obtained the height and speed for each enemy missile. Under the above decision process, your task is to compute the probability that each missile will be intercepted.

The interception process works as follows. Suppose there are n incoming missiles, arriving in a given order. Let the i-th missile have height \(h_i\) and speed \(s_i\). A valid interception sequence is a subsequence (taken in increasing order of arrival) \(i_1, i_2, \dots, i_k\) such that:

[ h_{i_1} \ge h_{i_2} \ge \cdots \ge h_{i_k} \quad \text{and} \quad s_{i_1} \ge s_{i_2} \ge \cdots \ge s_{i_k}. ]

The goal is to choose an interception sequence of maximum possible length \(L\). Note that there can be more than one maximum sequence. When a maximum sequence is selected uniformly at random, the probability that a missile is intercepted is the fraction of maximum sequences that contain that missile.

Input:

The first line contains an integer \(n\) indicating the number of missiles. Each of the following \(n\) lines contains two integers \(h_i\) and \(s_i\), representing the height and speed of missile \(i\) respectively.

Output:

Output \(n\) lines. The \(i\)-th line should contain the probability (in fixed-point format with 6 decimal places) that the \(i\)-th missile will be intercepted.

inputFormat

The input starts with an integer \(n\) (the number of missiles). The next \(n\) lines each contain two integers \(h_i\) and \(s_i\) (\(1 \leq i \leq n\)), denoting the height and speed of the \(i\)-th missile. The missiles are given in the order of arrival.

outputFormat

Output \(n\) lines. The \(i\)-th line should display the interception probability for the \(i\)-th missile, formatted as a floating-point number with 6 decimal places.

sample

3
100 200
90 190
80 180

1.000000
1.000000
1.000000