Programming Team’s Will

The UCF Programming Team has a not-so-well-known tradition of creating “Last Wills” for the event that one of the members leaves the team during the year unannounced. If that happens, something must be done with their lollipop collection in the Programming Team Lab! The Programming Team lets its members specify to which other UCF students they want to give their lollipops. Each member writes up a list of UCF students and, for each student, what fraction of the lollipop collection should be given to them. Note that all team members are UCF students as well so a team member could have another member in their will.

Normally this is a perfect solution; someone drops out of UCF to switch to some lesser college, and their lollipops are spread among their specified recipients. However, there has been a horrible tragedy. Some of the team was enrolled in Dr. Meade’s CS-I class, and just took the first exam. Everyone who was enrolled has failed out of the class, and is kicked off the team by Dr. Meade! But what should happen to their lollipop collections now? The issue is that some team members had each other in their wills, so we cannot simply resolve them one at a time.

To handle this, the team agreed upon a fair strategy to distribute the lollipops. The wills would all be repeatedly applied (including giving lollipops to departing team members) until the total lollipops of departing members converged to zero. In the event that infinite applications of everyone’s wills would still leave some lollipops with departing members, those lollipops would be thrown away. However, this is potentially a very slow and infinite process, so they need your help to figure out where the lollipops end up. Note that a fractional part of a lollipop can be given, if needed, by crushing up the lollipop.

Given a list of departing team members’ wills and their lollipop counts, output how many lollipops each student at UCF will end up with.

The first input line contains two space separated positive integers: N (2 ≤ N ≤ 500) representing the number of programming team members in Dr. Meade’s class, and M (N < M ≤ 50,000) representing the total number of UCF students. The programming team members in Dr. Meade’s class have ID’s 1 through N, and the other students have ID’s N+1 through M. Then follow N wills, each described as follows:

Each will starts with a line containing two integers: L (1 ≤ L ≤ 1000) representing the number of lollipops, and K (1 ≤ K < M) the number of entries in this will. The following K lines each contain an integer X specifying the id of the person in the will, and a floating-point number P (P ≥ 10-6) specifying what portion (fraction) of the lollipop collection goes to person X in this will. Assume that:

• A single person's will contains only unique people, i.e., there won't be two entries for the same person in a will.
• The will for a person will not contain themselves.
• The fractions in a team member’s will add up to 1.
• The total number of entries in all wills will not exceed 1,000,000.
• The input values for P will be given with no more than 6 digits after the decimal point.

Output M lines, containing the number of lollipops that each student ends up with (in order by ID). Note that the first N lines should be 0, since all lollipops from those students will either be given away or thrown away. Your answer will be judged to a precision of 10-5.