题目背景

小骑士刚刚学会了超级冲刺，正在地图里面横冲直撞。

不幸的是，这里地形相当复杂，而且某些地方布满了尖锐的水晶，不能停留。

题目描述

给定一张 n 个点，m 条边的无向图，保证没有重边和自环。

定义一步『冲刺』为从一个点出发，移动至任意一个相邻的点，并停留在上面。

定义一步『超级冲刺』为从一个点出发，连续移动到相邻节点 d 次，且不能走回头路，然后停留在最后一步到达的节点上。

注意，此次移动允许重复走一条边，但不允许在此次操作内连续两次经过相同的边。而且不会停留在中途经过的节点上。

此外，有一些节点是不能停留的。

你现在在 1 号节点，现在你要求出来从 1 号节点到每个点的最小步数，不可达输出 −1。

输入

第一行输入四个正整数 sid,n,m,d，表示测试点编号，原图的点数，边数，和一次超级冲刺的距离。

第二行输入 n 个自然数 a1∼n，a**i=0 表示此位置不能停留，a**i=1 表示可以停留。

接下来 mm 行每行两个正整数 u,v 表示节点 u 和 v 之间有一条连边。

输出

输出一行 n 个整数，第 i 个数表示停留在节点 i 所需要的最小步数，如果不能到达，则输出 −1。

样例

输入复制

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

输出复制

0 1 -1 2 1

提示

提示

样例解释

第一步到 2 节点可以使用 1→2 或 1→2→3→4→2。

第一步到 5 节点可以使用 1→2→3→4→5

可以发现，不存在第一步到 44 号点的方案。

数据范围

特殊性质 A：保证给定的图是一棵树。

特殊性质 B：保证存在一种重标号方案使得 ∀i≤n−1，存在边 (i,i+1)。

特殊性质 C：保证存在一种重标号方案使得 ∀i≤n−1，存在边 (1,i+1)。

特殊性质 D：保证树随机生成，随机方式为，对于 2≤i≤n，随机一个数 j∈(1,i−1)，并将 i 向 j 连边，然后将这棵树随机重标号。

特殊性质 E：保证图随机生成，随机方式为，随机两个不同的整数 1≤u,v≤n，若原图不存在这条边就加入，否则重新随机，重复 mm 次。

保证 1≤u,v≤n≤105,m≤2×105,d≤20,a**i∈[0,1],1≤u,v≤n。

保证 a1=1。