There are $N$ people living in $N$ houses in the city of Treeland. The houses in the city of Treeland form a tree-like structure with $house_1$ as the root. You are given the structure of the city in the form of a tree with the houses as nodes. You are also given the ages of people living in each of the houses.

As we all know friendships form between people of almost equal ages. More formally, two person will become friends if and only if the absolute difference between their ages is no more than $K$.

You need to find the number of pairs of people who become friends within each of the $N$ subtrees, i.e, for each subtree with $house_i$ as root, you need to find the number of unordered pairs of integers $a$ and $b$ $(a \neq b)$, such that $a$ and $b$ both belong to the subtree rooted at $house_i$ and become friends.

Input Format

The first line contains two integers $N$ and $K$, the number of people/houses in Treeland and the maximum possible difference between the ages of two people who can be friends. The second line contains $N$ space separated integers, where the $i^{th}$ integer, $age_i$ denotes the age of the person living in $house_i$. The next $N-1$ lines contains the structure of Treeland in the form of $N-1$ edges. The $i^{th}$ edge is represented by two integers $a_i$ and $b_i$, denoting an edge between $house_{a_i}$ and $house_{b_i}$.

Output Format

Print a single line containing $N$ space separated integers integers, where the $i^{th}$ integer is the answer for the subtree rooted at $house_i$.

Constraints

$1 \leq N \leq 10^5$

$0 \leq K \leq 10^9$

$1 \leq age_i \leq 10^9$

$1 \leq a_i, b_i \leq N, a_i \neq b_i$