Larry the magical panda is playing a new game once again! This time, having gotten bored of playing with bamboo sticks, Larry is playing the game on an entire bamboo tree with ~N~ nodes labeled from ~1~ to ~N~. Being a tree, it has ~N-1~ edges and each edge has distance ~1~. Furthermore, each node has an additional value ~a_i~ associated with it. Being a magical panda, Larry can teleport from a node ~u~ to any node ~v~ with distance less than or equal to a given constant ~D~ from ~u~. The teleportation comes at the cost of ~a_v~. For each node ~v~, what is the minimum cost for Larry to reach ~v~ if he starts the game at node ~1~?

Constraints

~1 \le D < N \le 2 \times 10^5~

~1 \le a_i \le 10^9~

Subtask 1 [10%]

~a_i = 1~

Subtask 2 [90%]

No additional constraints.

Input Specification

The first line will contain two integers, ~N~ and ~D~.

The following line will contain ~N~ integers ~a_i~.

The following ~N-1~ lines will each contain two integers, ~u_i~ and ~v_i~, denoting an edge between nodes ~u_i~ and ~v_i~.

Output Specification

Output ~N~ space separated integers, the ~v~-th of which represents the minimum cost for Larry to reach node ~v~.

Sample Input 1

2 1
1 1
1 2

Sample Output 1

0 1

Sample Input 2

6 3
100 100 100 100 100 1
1 2
2 3
3 4
4 5
3 6

Sample Output 2

0 100 100 100 101 1