一些公司决定在某星球举办产品展览会。已知该星球有n个国家，有n条道路连接某两个国家。你可以从一个国家到另一个有路连着的国家，若两国家没有道路相连即无法直接到达，但一定可通过绕路到达。

现在需要在展览会上展示k件物品，但每个国家只能提供一件物品。那为了展览会的高端性，所以必须有s件物品是不同种类的。

那最关键的当然是运费问题，从u国运到v国需要花费d(u,v)的钱，那d(u,v)是u国到v国的最短路径的长度，即AB相连，BC相连，那从A运到B花费1，运到C花费2.

主办方需要承担所有的运费，所以他选择花费￥0雇佣你帮他分别计算在这n个国家办展览所要花费的最低运费。

第一行输入四个数n,m,k,s，分别代表国家数，道路数，展览商品数，商品种类数

( 1≤n≤10^5 , 0≤m≤10^5 , 1≤s≤k≤min(n,100) )

第二行n个整数ai (1≤ai≤k )其中ai 是第i个城镇生产的商品类型。确保1和k之间的所有整数在整数ai中至少出现一次。

接下来m行，每行两个数u,v(1≤u,v≤n ,u≠v ) 代表u国与v国相连 ,保证两国之间只有一条道路相连，且可以通过道路从任何城镇到任何其他城镇

打印n个数，其中第i个数是在第i个国家举办展览要花的运费，用空格分隔数字。