暂无测试数据。

一个数据包在一个无向网络中传递。在时刻 $0$，该数据包将依照特定的概率随机抵达网络中的某个节点。

网络可以看做一张完全带权无向图，包含 $N$ 个节点，若 $t$ 时刻数据包在节点 $i$，则在 $t+1$ 时刻，数据包被传递到节点 $j$ 的概率是$$\displaystyle \frac{d(i,j)}{\displaystyle \sum_{k \ne i}d(i,k)}$$

其中 $d(i,j)$ 表示节点 $i$ 到节点 $j$ 的最短路径的长度。在传递到下一个节点后，该数据包会自动删除在当前节点的备份。

现在，给定数据包 $0$ 时刻在每个节点的概率和网络的每条边权。求 $T$ 时刻数据包在每个节点的概率。

输入格式

第一行两个整数 $N$ 和 $T$。

第二行 $N$ 个实数，表示 $0$ 时刻数据包在每个节点的概率（保证概率加起来为 $1$）。

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

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

输出格式

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

数据范围与约定

对于 $50\%$ 的数据，$T \le 20$。

对于 $100\%$ 的数据，$N \le 200,T \le 10^9$。保证对于每个点 $d$ 的和值在 int 范围。

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

0.400000
0.350000
0.250000