J. Juicy Revenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Problem E looks so hard...

Magaly and Danna are competing in a game called "Choose Then Win". The game is played with an ordered list of $$$n$$$ boxes, numbered from $$$1$$$ to $$$n$$$.

For a chosen integer $$$k$$$ ($$$1 \le k \le n$$$), a player selects a sequence of $$$k$$$ distinct boxes. Once selected, the chosen boxes are opened strictly in increasing order of their original indices, $$$i_1 \lt i_2 \lt \dots \lt i_k$$$.

When opening the $$$j$$$-th chosen box ($$$1 \le j \le k$$$), the box with index $$$i_j$$$ awards a score of $$$x_{i_j}$$$ with probability $$$\frac{p_{i_j} \cdot j}{q_{i_j}}$$$ Otherwise, it awards $$$0$$$ score.

Magaly wants to beat Danna by maximizing her total expected score. Assuming Magaly selects her $$$k$$$ boxes optimally, determine the maximum expected score she can obtain for every integer $$$k$$$ from $$$1$$$ to $$$n$$$.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^3$$$) the total number of boxes.

The next $$$n$$$ lines each contain three space separated integers $$$x_i$$$, $$$p_i$$$, $$$q_i$$$ ($$$1 \le x_i \le 10^9$$$, $$$0 \le p_i \le q_i \le 10^9$$$, $$$q_i \neq 0$$$), representing the score value and probability parameters for the $$$i$$$-th box. Its guaranteed that $$$p_i \cdot i \lt = q_i$$$

Output

Print $$$n$$$ space-separated real numbers $$$C_1, C_2, \dots, C_n$$$, where $$$C_k$$$ represents the maximum expected total score Magaly can achieve when selecting $$$k$$$ boxes.

Your output will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
1
1 1 1
Output
1.0000000000
Input
4
1 1 10
9 1 10
8 1 10
9 1 10
Output
0.9000000000 2.7000000000 5.2000000000 7.9000000000
Input
3
1000000000 1 1
1000000000 1 2
1000000000 1 3
Output
1000000000.0000000000 2000000000.0000000000 3000000000.0000000000