A. Average Rank
time limit per test
5.0 s
memory limit per test
256 MB
input
standard input
output
standard output

The National Weekly Escape Room Challenge (NWERC) is a long-running competition held in Eindhoven. Every week a new escape room is presented, and anyone who completes it in their first attempt gains one point.

At the end of each week, competitors are ranked by the total number of points accumulated so far, highest first. In the case of a tie, they share the same rank. In other words, the rank of a competitor is one more than the number of people with a strictly larger number of points.

Illustration of Sample Input 3.
In total there have been $$$n$$$ participants in the contest, and the contest has been going for $$$w$$$ weeks. For each week you are given a list of the competitors that gained a point that week. Your task is to calculate the average rank during the $$$w$$$-week competition for each competitor.

The figure illustrates the score progression in the third sample.

Input

The input consists of:

  • One line with two integers $$$n$$$ and $$$w$$$ ($$$1 \le n, w \le 3 \cdot 10^5$$$), the number of competitors and the number of weeks. The competitors are numbered from $$$1$$$ to $$$n$$$.
  • $$$w$$$ lines (one for each week), each containing an integer $$$k$$$ ($$$0 \le k \le n$$$) followed by $$$k$$$ distinct integers $$$c_1, \ldots, c_k$$$ ($$$1 \le c_i \le n$$$ for all $$$i$$$), indicating that the $$$k$$$ competitors $$$c_1, \ldots, c_k$$$ each gained a point that week.

The total number of points awarded is at most $$$1$$$ million.

Output

Output $$$n$$$ lines, the $$$i$$$th of which contains the average rank of the $$$i$$$th competitor during the $$$w$$$-week competition. Your answers should have an absolute or relative error of at most $$$10^{-6}$$$.

Examples
Input
3 2
2 1 2
2 1 3
Output
1.000000000
1.500000000
2.500000000
Input
3 1
0
Output
1.000000000
1.000000000
1.000000000
Input
5 6
2 3 5
2 3 1
0
3 3 5 2
3 5 4 2
2 3 4
Output
3.166666667
3.333333333
1.000000000
3.833333333
1.666666667