暂无测试数据。

蒜头君有一张包含 $N$ 个节点的完全带权无向图，在 $0$ 时刻，他会在图中选择一个节点，并在该节点放置一个“智能小球”，随后每 $1$ 时刻智能小球会根据当前图的信息，移动到其他节点处。已知蒜头君在 $0$ 时刻时选择第 $i$ 个节点的概率为 $p_i$。

假设在 $t$ 时刻时，智能小球在节点 $i$，则在 $t+1$ 时候智能小球移动到节点 $j$ 的概率为：

$$\displaystyle \displaystyle \frac{dis(i,j)}{\displaystyle \sum_{k \ne i}dis(i,k)} $$

其中 $dis(i,j)$ 表示节点 $i$ 到节点 $j$ 的最短路径的长度。

蒜头君想要知道 $T$ 时刻时智能小球在每个节点的概率。

输入格式

第一行两个整数 $N$ 和 $T$，表示完全带权无向图中有 $N$ 个节点，以及时刻 $T$。

第二行 $N$ 个实数 $p_i$，第 $i$ 个数，表示蒜头君在 $0$ 时刻选择第 $i$ 个节点的概率（保证概率加起来为 $1$）。

接下来 $N$ 行每行 $N$ 个整数，第 $i$ 行第 $j$ 个数表示节点 $i$ 和节点 $j$ 之间的边权。

保证第 $i$ 行第 $i$ 个数为 $0$ 且第 $i$ 行第 $j$ 个数等于第 $j$ 行第 $i$ 个数。

输出格式

输出共 $N$ 行，第 $i$ 行表示 $T$ 时刻智能小球在节点 $i$ 的概率，保留六位小数。

数据范围

• 对于 $50\%$ 的数据，$1\leq T \le 20$。
• 对于 $100\%$ 的数据，$1\leq N \le 200,1\leq T \le 10^9,0\leq p_i \leq 1,\sum p_i = 1$。保证对于每个点 $d$ 的和值在 int 范围。

3 2
0 1 0
0 1 4
1 0 2
4 2 0

0.400000
0.350000
0.250000