ICPCCamp has $n$ shops, numbered $1, 2, \dots, n$. For any $i > 1$, there is a one-way road from shop $p_i$ to $i$. Additionally, shop $i$ sells goods of type $a_i$.

Bobo travels from shop $1$ to shop $i$. He must purchase goods at two different shops (including shops $1$ and $i$). Let $x$ be the type of the good he purchases first, and $y$ be the type of the good he purchases second. Let $f_i$ denote the number of distinct ordered pairs $\langle x, y \rangle$. Calculate the values of $f_2, f_3, \dots, f_n$.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case starts with a line containing one integer $n$.

The second line contains $(n - 1)$ integers $p_2, p_3, \dots, p_n$.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output

For each test case, output $(n - 1)$ integers representing $f_2, f_3, \dots, f_n$.

Examples

Input 1

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

Output 1

1
3
1
1
1
3
5

Note

For the third example, when $i = 4$, the possible ordered pairs $\langle x, y \rangle$ are $\langle 1, 2 \rangle, \langle 1, 3\rangle, \langle 2, 3 \rangle, \langle 3, 2\rangle, \langle 3, 3\rangle$, totaling $5$ pairs. Thus, $f_4 = 5$.

Constraints

• $1 \leq n \leq 10^5$
• $1 \leq p_i < i$
• $1 \leq a_i \leq n$
• The sum of $n$ does not exceed $5 \times 10^5$.