There are $n$ cute dogs, and the $i$-th cute dog has a cuteness value of $a_i$. The cute dogs form a tree structure through sibling relationships. Given that dog $1$ is the root of the tree, the dogs in the subtree of dog $i$ are the sisters of dog $i$.

If a cute dog $i$ plays a game, she contributes $f_d(a_i^2)$ to the joy value of the game. If two cute dogs $i$ and $j$ play a game together, they contribute $f_d(a_i a_j)$ to the joy value of the game. The joy value of a game is the sum of the joy values contributed by all dogs and pairs of dogs playing the game.

Given a constant $d$, we decompose $z$ into a product of prime powers $z = \prod_i p_i^{k_i}$ and define:

$$ f_d(z) = \prod_i (-1)^{k_i} [k_i \le d] $$

Now, for each cute dog $x$, she intends to play a game with her sisters. Please help them calculate the joy value of this game.

Input

The first line contains two integers $n$ and $d$.

The next $n-1$ lines each describe an edge, where the $i$-th edge is $u_i, v_i$. It is guaranteed that these $n-1$ edges form a tree.

The next line contains $n$ integers, where the $i$-th integer represents $a_i$. It is guaranteed that all $a_i$ form a permutation of $1$ to $n$.

Output

Output $n$ lines, each containing one integer. The number on the $i$-th line represents the answer for the dog with index $i$.

Examples

Input 1

3 2
1 2
1 3
1 2 3

Output 1

2
1
1

Note 1

The answer for dog $1$: $f_d(1^2) + f_d(2^2) + f_d(3^2) + f_d(1 \times 2) + f_d(1 \times 3) + f_d(2 \times 3) = 1 + 1 + 1 - 1 - 1 + 1 = 2$.

The answer for dog $2$: $f_d(2^2) = 1$.

The answer for dog $3$: $f_d(3^2) = 1$.

Input 2

20 1
15 2
4 15
9 13
16 19
2 5
13 2
19 2
8 14
1 12
18 7
10 5
3 8
20 19
14 2
7 19
18 6
8 11
17 8
19 1
14 3 5 2 9 4 18 16 1 20 13 7 6 12 19 17 10 15 8 11

Output 2

2
2
0
0
0
0
0
0
1
0
0
0
2
0
1
0
0
0
3
0

Constraints

For $100\%$ of the data, $1 \le n \le 2 \times 10^5$, $1 \le d \le 20$, $1 \le a_i, u_i, v_i \le n$, and all $a_i$ form a permutation of $1$ to $n$.