The PRTS system of Rhodes Island is conducting a wargame simulation.

The tactical network for the simulation is a rooted tree with $n$ nodes, rooted at node 1. For every node $i$ ($2 \le i \le n$) in the tree, there is a directed edge to its parent node $f_i$, and this edge has a fixed traffic capacity $w_i$.

The PRTS system needs to perform an independent tactical evaluation for each subtree in this tree. For a subtree rooted at node $x$, the simulation rules are as follows:

• Before the exercise begins, you can deploy any number of reconnaissance drones on any node within the subtree, excluding $x$.
• After the exercise begins, the drones will perform multiple rounds of synchronous movement. In each round, all drones currently staying at any node $i$ (where $i \neq x$) within the subtree will simultaneously move along the directed edge $(i, f_i)$ to its parent node $f_i$. Specifically, drones that reach node $x$ will leave the simulation area and be recovered by the system, no longer participating in subsequent movements.
• Before the start of any movement round, if there exists a node $i$ ($i \neq x$) in the subtree such that the total number of drones currently staying there is strictly greater than the traffic capacity $w_i$ of the edge $(i, f_i)$, congestion occurs, and the simulation for this subtree is declared a failure.

We define the tactical weight of a subtree as the maximum total number of drones that can be deployed in the subtree before the exercise begins, under the condition that no congestion occurs throughout the entire simulation. Specifically, the tactical weight of a subtree containing only a single node (i.e., a leaf node) is 0.

Given the complete tactical network described above, calculate the tactical weight for each subtree rooted at nodes $1, 2, \dots, n$.

Input

Each test case contains multiple test cases. The first line contains an integer $T$ ($3 \le T \le 10^5$) representing the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 10^6$) representing the number of nodes. The second line contains $n - 1$ integers $f_2, f_3, \dots, f_n$ ($1 \le f_i < i$) representing the parent node of each node. The third line contains $n - 1$ integers $w_2, w_3, \dots, w_n$ ($1 \le w_i \le 10^9$) representing the traffic capacity of each edge.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \times 10^6$.

Output

For each test case, output a single line containing $n$ integers representing the answer, where the $i$-th integer is the tactical weight of the subtree rooted at $i$.

Examples

Input 1

3
3
1 1
325 799
5
1 1 2 2
3 1 2 4
10
1 2 3 4 5 6 7 8 9
8 3 6 2 9 5 1 7 4

Output 1

1124 0 0
7 6 0 0 0
23 15 15 9 17 8 3 11 4 0