#1462. 玩绝区零玩的

你说得对，但是《绝区零》是由米哈游自主研发的一款全新动作类游戏。游戏发生在一个被称作「新艾利都」的奇妙都市，在这里，你将扮演名为「绳匠」的神秘角色，在自由的打工中邂逅性格各异、能力独特的同伴们，帮助他们探索空洞，挑战强敌——同时，逐步发掘「绳网」的真相。

新艾利都里一共有 $n$ 个空洞，它们之间有 $m$ 条双向道路连接着，每经过一条道路需要花费 $1$ 的时间。

作为一名合格的绳匠，Shirost 在引导 uuku 探索空洞以前，需要对这 $n$ 个空洞进行完全的勘测。空洞十分不稳定，每当进入第 $i$ 个空洞时，将会遭遇第 $a_i(a_i \in \{1,2\})$ 个事件，其中：

• $a_i=1$ 表示遭遇了战斗事件， uuku 的体力值下降 $1$。
• $a_i=2$ 表示遭遇了休息事件， uuku 的体力值上升 $1$。

uuku 不希望这次探索之旅平平淡淡，他希望在包括起点和终点的探索过程中自己的体力值始终不低于 $-k$，也不高于 $k$，即体力值 $T$ 满足 $-k \leq T \leq k$。在进入空洞前 uuku 的体力值为 $0$。

为了规划合理的路线， Shirost 需要知道对于所有 $i(1 \leq i \leq n)$，以第 $1$ 个空洞为起点，第 $i$ 个空洞为终点的所有合法路径耗时最小值。

由于 Shirost 分不清游戏和现实，请你帮他解决这个问题。

输入第一行包含三个整数，分别代表空洞的数量 $n$，空洞间的道路数 $m$ ，以及体力值的阈值 $k$ 。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$​ 表示编号为 $i$ 的空洞中遭遇的事件，$a_i=1$ 表示战斗事件，$a_i=2$ 表示休息事件。

第 $3$ 到第 $m+2$ 行，每行两个整数 $u,v$ ，代表从第 $u$ 个空洞到第 $v$ 个空洞有存在一条双向道路，通过该道路需要花费 $1$ 的时间。

输出共一行包含 $n$ 个整数，第 $i$ 个整数表示从 $1$ 号点到第 $i$ 个点至少需要花费多少时间，如果无解，请输出 $−1$。

样例输入1

8 8 2
1 1 2 1 1 1 1 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3 3

样例输出1

0 1 2 3 5 7 9 -1

数据范围

$1 \le n \le 10^5$

$1 \le m \le 2\times 10^5$

$1 \le k \le 10$

$a_i \in \{1,2\}$

提示

进入 1 号空洞也会遇到相应事件。

可以重复进入空洞，每次进入时都将遭遇相应事件。