Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem types

You have won the labour lottery and are now an apartment manager at 100 KRUSHVICE st. There, your job is to ensure that the N tenants are satisfied, and more important, following the government directives.

In order to do the latter, you plan to install Ki cameras in tenant i's room. Camera j in the i-th person's room has a probability of Pi,j of discovering that person doing something illegal. (Note that discovering a person twice has no additional effect). However, due to budget cuts, your number of cameras is limited to C. Determine the maximum expected number of people caught doing something illegal if you only install up to C cameras, for ALL values of C from 1 to \sum_{i=0}^{N-1} K_i.

Constraints

1 \leq N \leq 5 \times 10^5

\sum_{i=0}^{N-1} K_i \leq 5 \times 10^5

The probability P_{i,j} is a real number between 0 and 1.

Input Format:

Line 1: An integer, N, the number of tenants.
Next N Lines: An integer K_i, the number of cameras planned to be installed in the ith person room, and K real numbers, the values of P_{i,j}.

Output Format:

\sum_{i=0}^{N-1} K_i lines, each with a single real number, the maximum expected value after installing C (1 \leq C \leq \sum_{i=0}^{N-1} K_i) cameras. Your answer will be accepted if it differs from the expected answer by up to 10^{-6}.

Sample Input:

3
3 0.5 0.5 0.5
2 0.4 0.25
1 0.3

Sample Output:

0.50000000
0.90000000
1.20000000
1.45000000
1.60000000
1.72500000

Also note that

0.50000000
0.90000000
1.20000000
1.44999999
1.60000000
1.72500001

is also a valid output, for example


Comments

There are no comments at the moment.