Snuke has a rooted tree with $n$ nodes. Each node has a weight $w_i$, and initially, there are no stones on any node.

Snuke has prepared some stones and is holding them in her hand. She can perform the following two operations any number of times:

1. Place $w_i$ stones on node $i$ from her hand. This operation can only be performed if every child node $j$ of node $i$ already has exactly $w_j$ stones on it.
2. Remove all stones from node $i$ and return them to her hand.

Takahashi wants to know, for each node $i$, what is the minimum number of stones Snuke needs to prepare in her hand in order to successfully place $w_i$ stones on node $i$ (according to the above rules).

Input Format

Read from standard input.

• The first line contains a single integer $T$, indicating the subtask ID.
• The second line contains a single integer $n$ $(n \leq 2 \times 10^5)$.
• The third line contains $n-1$ positive integers. The $i$-th of these numbers is $p_i$, the parent of node $i+1$. It is guaranteed that $p_i < i+1$.
• The fourth line contains $n$ positive integers, where the $i$-th number is $w_i$ — the weight of node $i$.

Output Format

Output to standard output.

Print one line with $n$ integers. The $i$-th integer is the answer for node $i$: the minimum number of stones Snuke must prepare in order to place $w_i$ stones on node $i$.

Examples

Input

0
3
1 2
1 1 1

Output

2 2 1

Input

0
3
1 1
1 1 1

Output

3 1 1

Scoring

For all test cases:

• $n \leq 2 \times 10^5$
• $1 \le p\_i < i$
• $1 \le w\_i \le 10^9$