To defend against enemy missile attacks, a country has developed a missile interception system. However, this system has a flaw: while its first shell can reach any altitude and intercept a missile of any speed, each subsequent shell cannot be fired at an altitude higher than the previous one, and the speed of the missile it intercepts cannot be greater than that of the previous one. One day, radar detected an incoming enemy missile attack. Since the system is still in the trial phase, there is only one such system available, which may not be able to intercept all missiles.

In cases where not all missiles can be intercepted, we naturally want to choose a plan that minimizes national losses, which means maximizing the number of intercepted missiles. However, there may be multiple plans that yield the maximum number of intercepted missiles. If there are multiple optimal plans, we will randomly select one to serve as the final blueprint for the interception operation.

Our spies have obtained the altitude and speed of all enemy missiles. Your task is to calculate the probability that each missile will be intercepted when the above decision-making process is executed.

Input

The first line contains a positive integer $n$, representing the number of enemy missiles. The following $n$ lines provide the information for all enemy missiles in order: The $(i+1)$-th line contains two positive integers $h_i$ and $v_i$, representing the altitude and speed of the $i$-th missile, respectively.

Output

The output contains two lines. The first line contains a positive integer, representing the maximum number of missiles that can be intercepted. The second line contains $n$ real numbers between 0 and 1, where the $i$-th number represents the probability that the $i$-th missile is intercepted (you may provide any number of significant digits).

Constraints

For 30% of the data, $1 \le n \le 1000$. For 100% of the data, $1 \le n \le 5 \times 10^4$, $1 \le h_i, v_i \le 10^9$. Approximately 30% of the data is uniformly distributed, where all $v_i$ are equal. Approximately 50% of the data is uniformly distributed, satisfying $1 \le h_i, v_i \le 1000$.

Subtasks

For each test case, if the first line of the output file matches the standard output, you will receive 40% of the points for that test case. If each number in the second line of the output file has an error no greater than $10^{-4}$ compared to the standard output, you will receive 60% of the points for that test case. These two parts are cumulative.

This problem uses a custom checker. To prevent the custom checker from failing, even if you cannot correctly determine the answer to a question, you should still output a random number in the corresponding position.

Examples

Input 1

4
3 30
4 40
6 60
3 30

Output 1

2
0.33333 0.33333 0.33333 1.00000