racing

竞速领域大神 ekxk344 决定考一考你对竞速游戏的理解。

赛车地图可以抽象为 $n$ 个节点 $m$ 条边的带权强连通有向图。

边 $(u_i, v_i)$ 有边权 $p_i$，表示在 $u_i$ 的赛车一个单位时间后有 $\frac{p_i}{10^6}$ 的概率到达节点 $v_i$，保证每个节点的出边边权之和为 $10^6$。

地图一共分为 $T$ 个区域，节点 $x$ 有所属的区域 $c_x$，保证每条边 $(u_i, v_i)$ 都满足 $c_{u_i} + 1 \equiv c_{v_i} \pmod T$。

你需要对每个节点 $x$ 求出赛车从 $x$ 出发期望多少单位时间后第一次回到节点 $x$。

输入格式

第一行包含三个正整数 $n, m, T$，分别表示赛车地图的节点数、边数与区域数。

接下来一行包含 $n$ 个正整数，第 $x$ 个表示节点 $x$ 所在的区域 $c_x$。

接下来 $m$ 行，每行包含三个正整数 $u_i, v_i, p_i$，表示有边权为 $p_i$ 的边 $(u_i, v_i)$。

输入保证 $1 \le u_i, v_i \le n, 1 \le p_i \le 10^6, 1 \le c_x \le T$。

输入保证 $c_{u_i} + 1 \equiv c_{v_i} \pmod T$，且每个节点出边边权之和为 $10^6$。

输入保证该有向图强连通。

输出格式

输出 $n$ 行每行一个小数，第 $x$ 行的小数表示节点 $x$ 的答案。

对于每个测试点，输出的每个数与标准答案绝对或相对误差不超过 $10^{-6}$ 即可通过该测试点。

提示

共有 $20$ 个测试点，每个测试点 $5$ 分。

对于所有测试点，$1 \le T \le n \le 5 \times 10^4, 1 \le m \le 10^5$。

测试点 $1 \sim 2$ 有 $n \le 10, m \le 20, T = 1$。

测试点 $3 \sim 5$ 有 $n \le 50, m \le 100, T = 1$。

测试点 $6 \sim 8$ 有 $n \le 100, m \le 10^5, T = 1$。

测试点 $9 \sim 14$ 有 $n \le 500, m \le 10^5, T = 1$。

测试点 $15 \sim 20$ 有 $n \le 5 \times 10^4, m \le 10^5, T = 100$