26194번 - Money Laundering 스페셜 저지다국어

문제

Consider a company A that made a 100 euros of profit this year. The company's owners are Ivan with 52.8% ownership share and Robi with a 47.2% ownership share. Naturally, the profits are shared proportionally to the shares with Ivan receiving 52.8 euros and Robi 47.2 euros.

They will have to pay tax on the received profits, but would like to avoid doing so, if at all possible. Sadly, the ownership structure of their company is too simple and it's easily discoverable how much profits each of them received.

For the next year, they prepare a plan. They make a shell company B and change the ownership shares. Ivan now only owns 1% of company A, Robi only 2%, the company B owns a 49% share of A and A owns 48% of itself. Company B has a similar ownership structure. 70% ownership share belongs to B itself, 25% to A, 3% to Ivan and 2% to Robi.

Looking naively, Ivan and Robi have very small ownership shares. However, we are interested in the ownership shares of ultimate beneficial owners, the persons who will ultimately profit, which are Ivan and Robi in our case. We wish to determine their ultimate ownership shares, which turn out to be approximately equal to what they were before the introduction of B.

Ultimate ownership shares can be determined as follows: let the company A have 100 euros of profit and B have 0 euros. The profits are paid out to all direct owners in proportion to their ownership share. However, since A and B are partial owners of themselves, they receive a part of the profit. To determine the ultimate share of the ultimate beneficial owners, we repeat the procedure – any profits that A and B receive are paid out again, with Ivan and Robi getting a share, as well as A and B. This is repeated ad infinitum until (theoretically, after an infinite number of steps) all money is paid out to the ultimate beneficial owners, and the ratio of the final sums received by Ivan and Robi is by definition equal to their ultimate share of A.

For a given structure of companies, determine the shares of the ultimate beneficial owners. However, the companies do not form a random network of ownership, but are structured in industrial sectors. Companies within sectors may form arbitrary ownership structures, but this is not true for companies in different sectors. If companies P and Q belong to different sectors, it cannot happen that

• P would own a (potentially indirect) share of Q and
• Q would own a (potentially indirect) share of P.

One or none of these statements could be true, but not both.

입력

The first line contains two space-separated integers $c$ and $p,ドル representing the number of companies and number of persons, respectively. Then $c$ lines follow, and $i$-th of them contains the description of $i$-th company. The line contains an integer $k_i,ドル the number of owners, and then $k_i$ entries of the form $o_{i,j}\colon,円 p_{i, j},ドル where $o_{i,j}$ is the designation of the $j$-th owner (person or company) and $p_{i, j}$ is their share in percentages. The share will have exactly one decimal place.

출력

Output the ultimate ownership shares of all persons in all companies. The $i$-th line should include shares of all persons in the $i$-th company, including persons with no share. The share is between 0 and 1. Shares in a line should be separated by a space. The answer will be considered correct if its absolute or relative error is less than 10ドル^{-4}$.

제한

• 1ドル \leq c, p \leq 10^3$
• 1ドル \leq \sum_{i=1}^n k_i \leq 10^4$
• $o_{i,j}$ can have two forms: P$x$ or C$y,ドル indicating that the owner is the $x$-th person or $y$-th company, respectively. It is guaranteed that 1ドル \leq x \leq p,ドル and 1ドル \leq y \leq c$ holds.
• $k_i \geq 1$
• 0ドル < p_{i,j} \leq 100$
• $\sum_{j=1}^{k_i} p_{i,j} = 100$
• The identifiers $\{o_{i,j}\}_{j=1}^{k_i}$ are unique, i.e. each owner is listed at most once.
• The number of companies belonging to each sector is less than 10ドル$.
• Each company has at least one ultimate beneficial owner. For example, a scheme where A would own a 100% of B and B a 100% of A is forbidden.

힌트