#P18581. Money Laundering

Money Laundering

Money Laundering

一家公司 A 今年获得了 100 欧元利润。Ivan 持有它 52.8% 的股份,Robi 持有 47.2%,因此二人分别获得 52.8 和 47.2 欧元。

为了让直接持股关系不再这么明显,他们成立了空壳公司 B,并调整持股结构:Ivan、Robi、B 和 A 自己分别持有 A 的 1%、2%、49% 和 48%;B 自己、A、Ivan 和 Robi 分别持有 B 的 70%、25%、3% 和 2%。

现在两个人的直接持股比例很小,但我们关心的是最终受益人:最终收到利润的自然人。他们对 A 的最终持股比例实际上仍与原来接近。

最终持股比例按以下过程定义。起初让一家公司获得一笔利润,其他公司的利润为零。每家公司按直接持股比例,将自己收到的钱分给其所有者。自然人收到的钱留在自己手里;公司收到的钱则在下一轮继续分给其所有者。这个过程无限重复,直到所有钱最终分配给自然人。某个人最终得到的钱占初始利润的比例,就是这个人对起始公司的最终持股比例。

给出所有公司的直接持股结构,请求出每个人对每家公司的最终持股比例。

公司按照产业划分为若干行业。同一行业内可以出现任意持股关系,但对于分属不同行业的公司 P 和 Q,下面两件事不能同时发生:

  • P 直接或间接持有 Q 的股份;
  • Q 直接或间接持有 P 的股份。

可以只发生其中一件,也可以都不发生。每个行业的公司数严格小于 10。输入不提供行业划分。

输入格式

第一行包含两个整数 c,pc,p,分别表示公司数和自然人数。公司编号为 1,…,c1,\ldots,c,自然人编号为 1,…,p1,\ldots,p。

接下来 cc 行,第 ii 行描述第 ii 家公司。该行先给出整数 kik_i,然后给出 kik_i 个形如“所有者:百分比”的条目:

  • Px 表示第 xx 个自然人;
  • Cy 表示第 yy 家公司;
  • 百分比恰有一位小数,例如 P1:50.0、C2:0.1。

公司可以持有自己的股份。

数据范围与保证

  • 1≤c,p≤10001\le c,p\le1000;
  • ki≥1k_i\ge1,且 ∑i=1cki≤10000\sum_{i=1}^{c}k_i\le10000;
  • 自然人编号在 [1,p][1,p] 内,公司编号在 [1,c][1,c] 内;
  • 每项持股百分比大于 00、不超过 100100,同一家公司的全部持股百分比之和恰为 100100;
  • 同一家公司的所有者互不相同;
  • 每个行业的公司数严格小于 1010,行业之间满足上文的持股限制;
  • 每家公司至少有一个最终受益的自然人。例如,A 由 B 持股 100%,而 B 又由 A 持股 100% 的封闭结构是不允许的。

输入只有一组数据。

输出格式

输出 cc 行。第 ii 行输出 pp 个实数,第 jj 个数为第 jj 个自然人对第 ii 家公司的最终持股比例。比例的真值在 [0,1][0,1] 内;即使某个人没有股份,也要在对应位置输出零。

每个数的绝对误差或相对误差严格小于 10−410^{-4} 时认为正确。同行相邻数用空格分隔。

样例输入 1

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

样例输出 1

0.501000 0.499000
0.234000 0.766000

样例输入 2

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

样例输出 2

0.500000 0.500000
0.450000 0.550000

样例输入 3

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

样例输出 3

0.528358 0.471642
0.540299 0.459701

样例输入 4

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

样例输出 4

0.373228 0.626772
0.411024 0.588976
0.2 0.8