题目描述

在某个牌局中，一副牌共有 $30$ 张，分成若干种类型。对于每种类型，牌堆中要么有 $1$ 张这种牌，要么有 $2$ 张这种牌。

正常情况下，牌堆洗好后，应当每次从剩余牌中随机抽出下一张，直到抽空。

然而你连续观察了 $100000$ 局后，发现荷官并不公平。他并不是等概率从剩余牌中抽下一张，而是使用了某种带权随机算法。

设第 $i$ 种牌的真实权重为 $X_i$，满足

$$0<X_i\le 1.$$

若某一时刻第 $i$ 种牌还剩 $c_i$ 张，则下一张牌属于类型 $i$ 的概率为

$$\frac{c_iX_i}{S},$$

其中

$$S=\sum_j c_jX_j$$

是所有剩余牌的总权重。

你记下了 $100000$ 局游戏中每一局 $30$ 张牌的完整抽出顺序。请根据这些记录，预测每种牌的权重。

输入格式

第一行包含两个整数 $m,n$，表示游戏局数和牌的类型数。测试数据中总有

$$m=100000.$$

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 种牌在牌堆中的数量。

接下来 $m$ 行，每行包含一局游戏的日志，由 $30$ 个整数构成，表示这一局中牌被依次抽出的类型。

对于每一行日志，每个类型 $i$ 都恰好出现 $a_i$ 次。

输出格式

输出 $n$ 个实数

$$W_1,W_2,\ldots,W_n,$$

表示你预测的各类型权重。

输出需要满足：

$$10^{-100}<W_i\le 1.$$

答案会按如下方式判定：对于任意真实权重满足 $X_i\le X_j$ 的一对类型 $i,j$，需要有

$$\left| \frac{X_i}{X_i+X_j} - \frac{W_i}{W_i+W_j} \right|<0.02.$$

数据范围

• $m=100000$；
• $1\le n\le 30$；
• $a_i\in\{1,2\}$；
• $\sum_{i=1}^n a_i=30$；
• 每局日志长度为 $30$，且第 $i$ 种牌恰好出现 $a_i$ 次。

说明

原题给出了一个小规模输入示例用于解释格式，但正式测试中始终有 $m=100000$，因此该小样例不会出现在测试数据中。