import java.io.*;
import java.util.*;
public class R485PD {
static FastInput k
= new FastInput
(System.
in); static FastOutput z = new FastOutput();
static int nodes, edges, kk, s;
static Graph graph;
static ArrayList<Integer> [] types;
static int [] nodeTypes;
static int [][] data;
static void startAlgorithm() {
for(int type = 1; type<=kk; type++) {
graph.bfs(type);
}
for(int i = 0; i<nodes; i++) {
int sum = 0;
ArrayList<Integer> temp = new ArrayList<Integer>();
for(int j = 0; j<data[i].length; j++) {
if(data[i][j] != 0) {
temp.add(data[i][j]);
}
}
for(int j = 0; j<s-1; j++) {
sum += temp.get(j);
}
if (i != 0) z.print(" ");
z.print(sum);
}
z.println();
z.flush();
}
@SuppressWarnings("unchecked")
static void getInputsAndInitializes() {
nodes = k.nextInt();
edges = k.nextInt();
kk = k.nextInt();
s = k.nextInt();
graph = new Graph(nodes, edges);
data = new int[nodes][kk+1];
nodeTypes = new int[nodes];
for(int i = 0; i<kk+1; i++) {
types[i] = new ArrayList<Integer>();
}
for(int i = 0; i<nodes; i++) {
int type = k.nextInt();
types[type].add(i);
nodeTypes[i] = type;
}
//i.inputArray(goodType, nodes, InputType.INTEGER);
k.inputUndirectedGraph(graph, edges);
}
while(k.hasNext()) {
getInputsAndInitializes();
startAlgorithm();
}
}
/* MARK: InputType enum */
public enum InputType {
INTEGER, LONG, WORD, LINE;
}
/* MARK: PrintType enum */
public enum PrintType {
SIDEBYSIDE, LINEBYLINE;
}
/* MARK: Graph implementation */
public static class Graph {
int nodes, edges;
ArrayList<Integer> [] neighbors;
@SuppressWarnings("unchecked")
public Graph(int nodes) {
this.nodes = nodes;
initializeGraph();
}
@SuppressWarnings("unchecked")
public Graph(int nodes, int edges) {
this.nodes = nodes;
this.edges = edges;
initializeGraph();
}
public void initializeGraph() {
for(int i = 0; i<nodes; i++) {
neighbors[i] = new ArrayList<Integer>();
}
}
public void addDirectedEdge(int u, int v) {
neighbors[u].add(v);
}
public void addUndirectedEdge(int u, int v) {
neighbors[u].add(v);
neighbors[v].add(u);
}
public void bfs(int type) {
int [] d = new int[nodes];
MyArrayDeque q = new MyArrayDeque();
for(int i = 0; i<types[type].size(); i++) {
int node = types[type].get(i);
q.enqueue(node);
d[node] = 0;
}
while(!q.isEmpty()) {
int u = q.dequeue();
for(int i = 0; i<neighbors[u].size(); i++) {
int v = neighbors[u].get(i);
if(d[v] > d[u] + 1 && nodeTypes[v] != type) {
d[v] = d[u] + 1;
q.enqueue(v);
data[v][type] = d[v];
}
}
}
}
}
/* MARK: MyArrayDeque implementation */
public static class MyArrayDeque {
int [] queue;
int frontCursor;
int backCursor;
public MyArrayDeque() {
queue = new int[nodes+1];
frontCursor = 0;
backCursor = 0;
}
public boolean isEmpty() {
return backCursor > frontCursor;
}
public void enqueue(int value) {
queue[frontCursor] = value;
frontCursor++;
}
public int dequeue() {
int returnValue = queue[backCursor];
backCursor++;
return returnValue;
}
}
/* MARK: FastInput and FastOutput implementation */
public static class FastInput {
}
public FastInput
(String path
){ try {
// TODO Auto-generated catch block
e.printStackTrace();
}
tokenizer = null;
}
return nextToken();
}
try {
return reader.readLine();
// TODO Auto-generated catch block
e.printStackTrace();
}
return null;
}
public boolean hasNext(){
try {
return reader.ready();
// TODO Auto-generated catch block
e.printStackTrace();
}
return false;
}
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
line = reader.readLine();
}
if (line == null) {
return null;
}
}
return tokenizer.nextToken();
}
return Integer.
parseInt(nextToken
()); }
return Long.
valueOf(nextToken
()); }
public void inputDirectedGraph(Graph graph, int edges) {
while(edges--> 0) {
int u = k.nextInt(); u--;
int v = k.nextInt(); v--;
graph.addDirectedEdge(u, v);
}
}
public void inputUndirectedGraph(Graph graph, int edges) {
while(edges--> 0) {
int u = k.nextInt(); u--;
int v = k.nextInt(); v--;
graph.addUndirectedEdge(u, v);
}
}
public <T> void inputList(ArrayList<T> list, int size, InputType inputType) {
switch (inputType) {
case INTEGER:
inputIntegerList(list, size); break;
case LONG:
inputLongList(list, size); break;
case WORD:
inputWordList(list, size); break;
case LINE:
inputLineList(list, size); break;
default: break;
}
}
@SuppressWarnings("unchecked")
public <T> void inputIntegerList(ArrayList<T> list, int size) {
for(int i = 0; i<size; i++) {
list.add((T)nextInt());
}
}
@SuppressWarnings("unchecked")
public <T> void inputLongList(ArrayList<T> list, int size) {
for(int i = 0; i<size; i++) {
list.add((T)nextLong());
}
}
@SuppressWarnings("unchecked")
public <T> void inputWordList(ArrayList<T> list, int size) {
for(int i = 0; i<size; i++) {
list.add((T)next());
}
}
@SuppressWarnings("unchecked")
public <T> void inputLineList(ArrayList<T> list, int size) {
for(int i = 0; i<size; i++) {
list.add((T)nextLine());
}
}
public <T> void inputArray(T [] array, int size, InputType inputType) {
switch (inputType) {
case INTEGER:
inputIntegerArray(array, size); break;
case LONG:
inputLongArray(array, size); break;
case WORD:
inputWordArray(array, size); break;
case LINE:
inputLineArray(array, size); break;
default: break;
}
}
@SuppressWarnings("unchecked")
public <T> void inputIntegerArray(T [] array, int size) {
for(int i = 0; i<size; i++) {
array[i] = (T)nextInt();
}
}
@SuppressWarnings("unchecked")
public <T> void inputLongArray(T [] array, int size) {
for(int i = 0; i<size; i++) {
array[i] = (T)nextLong();
}
}
@SuppressWarnings("unchecked")
public <T> void inputWordArray(T [] array, int size) {
for(int i = 0; i<size; i++) {
array[i] = (T)next();
}
}
@SuppressWarnings("unchecked")
public <T> void inputLineArray(T [] array, int size) {
for(int i = 0; i<size; i++) {
array[i] = (T)nextLine();
}
}
}
public FastOutput() {
}
public <T> void printSet(Set<T> set, int size, PrintType printType) {
switch (printType) {
case SIDEBYSIDE:
printSideBySideSet(set, size); break;
case LINEBYLINE:
printLineByLineSet(set, size); break;
default: break;
}
}
public <T> void printSideBySideSet(Set<T> set, int size) {
boolean isFirstElementPrinted = false;
for(T element : set) {
if(!isFirstElementPrinted) {
print(element);
isFirstElementPrinted = true;
return;
}
print(" "+element);
}
println();
}
public <T> void printLineByLineSet(Set<T> set, int size) {
for(T element : set) {
println(element);
}
}
public <T> void printList(ArrayList<T> list, int size, PrintType printType) {
switch (printType) {
case SIDEBYSIDE:
printSideBySideList(list, size); break;
case LINEBYLINE:
printLineByLineList(list, size); break;
default: break;
}
}
public <T> void printSideBySideList(ArrayList<T> list, int size) {
print(list.get(0));
for(int i = 1; i<size; i++) {
print(" "+list.get(i));
}
println();
}
public <T> void printLineByLineList(ArrayList<T> list, int size) {
for(int i = 0; i<size; i++) {
println(list.get(i));
}
}
public <T> void printArray(T [] array, int size, PrintType printType) {
switch (printType) {
case SIDEBYSIDE:
printSideBySideArray(array, size); break;
case LINEBYLINE:
printLineByLineArray(array, size); break;
default: break;
}
}
public <T> void printSideBySideArray(T [] array, int size) {
print(array[0]);
for(int i = 1; i<size; i++) {
print(" "+array[i]);
}
println();
}
public <T> void printLineByLineArray(T [] array, int size) {
for(int i = 0; i<size; i++) {
println(array[i]);
}
}
}
}