Description

考虑一家公司 $A$，今年获得了 $100\,\text{€}$ 的利润。公司的所有者为 Ivan（持股 $52.8\%$）和 Robi（持股 $47.2\%$）。自然地，利润将按持股比例分配，Ivan 获得 $52.8\,\text{€}$，Robi 获得 $47.2\,\text{€}$。

他们需要为获得的利润缴纳税款，但如果可能的话，他们希望避免缴税。可惜的是，他们公司的股权结构过于简单，很容易查明每个人获得了多少利润。

第二年，他们制定了一个计划。他们成立了一家空壳公司 $B$，并更改了股权结构。Ivan 现在只持有公司 $A$ 的 $1\%$，Robi 持有 $2\%$，公司 $B$ 持有 $A$ 的 $49\%$，而 $A$ 自己持有 $48\%$。公司 $B$ 的股权结构类似：$70\%$ 属于 $B$ 自己，$25\%$ 属于 $A$，$3\%$ 属于 Ivan，$2\%$ 属于 Robi。

乍一看，Ivan 和 Robi 的持股比例很小。然而，我们关注的是最终受益所有人的持股比例，即最终能获益的人，在本题中是 Ivan 和 Robi。我们希望确定他们的最终持股比例，结果发现这与引入 $B$ 之前几乎相同。

最终持股比例的确定方法如下：假设公司 $A$ 有 $100\,\text{€}$ 的利润，公司 $B$ 有 $0\,\text{€}$。利润按持股比例分配给所有直接股东。然而，由于 $A$ 和 $B$ 部分持有自己，它们也会获得一部分利润。为了确定最终受益所有人的最终持股比例，我们重复这一过程——$A$ 和 $B$ 获得的利润再次分配，Ivan 和 Robi 也会获得一部分，同时 $A$ 和 $B$ 也会获得一部分。如此无限循环下去，直到（理论上经过无限次分配）所有资金都分配给最终受益所有人，最终 Ivan 和 Robi 获得的总金额之比就定义为他们的最终持股比例。

对于给定的公司结构，计算所有最终受益所有人的持股比例。然而，公司之间并不是任意形成股权网络，而是按照行业分组。行业内的公司可以形成任意股权结构，但不同行业的公司之间不能这样。如果公司 $P$ 和 $Q$ 属于不同的行业，则不可能出现以下两种情况同时成立：

• $P$ 持有 $Q$ 的（可能是间接的）股份，并且
• $Q$ 持有 $P$ 的（可能是间接的）股份。

这两种情况中至多有一种成立，也可以都不成立。

Input Format

第一行包含两个用空格分隔的整数 $c$ 和 $p$，分别表示公司数和个人数。接下来有 $c$ 行，第 $i$ 行描述第 $i$ 个公司。每行包含一个整数 $k_i$，表示股东数量，接下来有 $k_i$ 个形如 $o_{i,j} : p_{i,j}$ 的条目，其中 $o_{i,j}$ 表示第 $j$ 个股东（个人或公司），$p_{i,j}$ 表示其持股比例（百分数，精确到一位小数）。

Output Format

输出所有公司中所有个人的最终持股比例。第 $i$ 行输出第 $i$ 个公司中所有个人的持股比例，包括持股为零的个人。持股比例为 $0$ 到 $1$ 之间。每行的持股比例用空格分隔。如果答案的绝对误差或相对误差小于 $10^{-4}$，则视为正确。

2 2
2 P1:50.1 P2:49.9
2 P1:23.4 P2:76.6

0.501000 0.499000
0.234000 0.766000

2 2
2 P1:50.0 P2:50.0
3 P1:20.0 P2:30.0 C1:50.0

0.500000 0.500000
0.450000 0.550000

2 2
4 P1:1.0 P2:2.0 C2:49.0 C1:48.0
4 C2:70.0 C1:25.0 P1:3.0 P2:2.0

0.528358 0.471642
0.540299 0.459701

3 2
5 P1:1.0 P2:2.0 C2:49.0 C1:38.0 C3:10.0
4 C2:70.0 C1:25.0 P1:3.0 P2:2.0
2 P1:20.0 P2:80.0

0.373228 0.626772
0.411024 0.588976
0.2 0.8

Hint

输入范围

• $1 \leq c, p \leq 10^3$
• $1 \leq \sum_{i=1}^{n} k_i \leq 10^4$
• $o_{i,j}$ 有两种形式：$\text{Px}$ 或 $\text{Cy}$，分别表示第 $x$ 个个人或第 $y$ 个公司。保证 $1 \leq x \leq p$，$1 \leq y \leq c$。
• $k_i \geq 1$
• $0 < p_{i,j} \leq 100$
• $\sum_{j=1}^{k_i} p_{i,j} = 100$
• 每个股东在同一公司中至多出现一次。
• 每个行业的公司数量小于 $10$。
• 每个公司至少有一个最终受益所有人。例如，$A$ 持有 $B$ 的 $100\%$，$B$ 持有 $A$ 的 $100\%$ 这种结构是被禁止的。

由 ChatGPT 4.1 翻译