Assume that you are given an undirected rooted tree with N nodes and an integer K. Node 1 is the root of the tree. Each node is uniquely numbered from 1 to N. Additionally, each node also has a color and the color is an integer value.

Note: Different nodes can have the same color.

For each node, you are required to find the $K^{th}$ closest ancestor from that node which has the same color.

Input Format:
The first line consists of two integers, denoting N and K $(1 \le N, K \le 10^6)$. The second line is an array A of length N, represented as space separated integers. Here $A_i$ $(1 \le A_i \le 10^6)$ is the color-value of $i^{th}$ node in the tree. This is followed by $N-1$ lines comprising of two space separated integers x and y, which denotes that there is an edge between nodes that are numbered x and y.

Output Format:
Print N space separated integers, where $i^{th}$ integer denotes the $K^{th}$ closest ancestor from $i^{th}$ node which has the same color. If no such ancestor exists, print 1.