Marisa lives in the Magic Forest, which can be visualized as a tree with $n$ vertices. Her house is located at vertex $1$. Over the next $n$ days, Marisa plans to visit a different vertex each day to harvest mushrooms. Specifically, on day $i$, she will travel to vertex $A_i$. During her journey to harvest mushrooms, Marisa wants to keep track of the number of vertices where she has already collected mushrooms. Can you assist her in counting this number?

Input

• The first line contains two integer $n$.
• The next $n - 1$ lines, each line contains two integer $u,v$, there is a path between $u$ and $v$.
• The next line contains $n$ integer $A_i$. It is guaranteed that the sequence $A$ represents a permutation of integers ranging from $1$ to $n$.

Output

• Print $n$ integers, the $i^{th}$ integer is the number of already hervested vertices on her journey on day $i$.

Constraints

• $1 \le n \le 10^5$.
• $1 \le u,v \le n$.

Example

Input:

5
1 4
5 4
1 3
2 4
4 2 1 5 3

Output:

0
1
0
2
1