시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB79423666.667%

문제

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 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.

Figure A.1: 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.

Figure A.1 illustrates the score progression in the third sample.

입력

The input consists of:

  • One line with two integers n and w (1 ≤ n, w ≤ 3 · 105), 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 ≤ k ≤ n) followed by k distinct integers c1, . . . , ck (1 ≤ ci ≤ n for all i), indicating that the k competitors c1, . . . , ck each gained a point that week.

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

출력

Output n lines, the ith of which contains the average rank of the ith competitor during the w-week competition. Your answers should have an absolute or relative error of at most 10−6.

예제 입력 1

3 2
2 1 2
2 1 3

예제 출력 1

1.000000
1.500000
2.500000

예제 입력 2

3 1
0

예제 출력 2

1.000000
1.000000
1.000000

예제 입력 3

5 6
2 3 5
2 3 1
0
3 3 5 2
3 5 4 2
2 3 4

예제 출력 3

3.166666667
3.333333333
1.000000000
3.833333333
1.666666667

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 A번

  • 문제를 만든 사람: Lukas Polacek