You are given a rooted tree with $n$ nodes, where the root is node $1$. Each edge has a character $c \in \{0, 1\}$. Let $S_u$ be the string formed by concatenating the characters on the edges along the path from the root to node $u$. It is guaranteed that for any node, the characters on the edges leading to its children are distinct.

For each node $u$, there is a value $val_u$ and a constraint $a_u$. We say node $v$ is an "extension point" of $u$ if $S_u$ is a suffix of $S_v$.

Alice has a string $S$, initially $S = S_u$. She can delete some number of characters from the end of $S$ to obtain $S'$, and then tells $S'$ to Bob.

Bob receives the string $S'$, and he needs to append some characters to $S'$ to obtain $S''$. For an extension point $v$ of $u$, if $S'' = S_v$ and $|S'| \ge a_v$, Bob gains a profit of $val_v$. Bob can perform this operation only once, so he will choose the $v$ that satisfies the conditions and maximizes $val_v$. If no such $v$ exists, Bob gains a profit of $0$.

Alice wants to know the sum of the maximum profits Bob can obtain across all $|S| + 1$ possible ways to delete $0 \sim |S|$ characters.

For each node $u$, you need to answer Alice's query.

Formally, for each node $u$, we need to calculate: $$ans_u = \sum_{0 \le i \le |S_u|} \max \{val_v \mid i \ge a_v \land S_u = S_v[|S_v| - |S_u| + 1, |S_v|] \land S_u[1, i] = S_v[1, i]\}$$ Specifically, if for a given $u$ there exists no $v$ satisfying the conditions, the $\max = 0$. Here, $S[l, r]$ denotes the substring of $S$ from index $l$ to $r$. Specifically, $S[x+1, x]$ denotes an empty string. $|S|$ denotes the length of string $S$, and $\land$ denotes the logical AND.

Input

The input is read from the file tree.in.

There are multiple test cases. The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $n$, representing the number of nodes.

The next $n-1$ lines each contain two integers $fa_i, c_i$, representing the parent of node $i$ and the character on the edge, respectively.

The next line contains $n$ positive integers $val_1, val_2, \dots, val_n$.

The next line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$.

Output

The output is written to the file tree.out.

Output one line containing $n$ integers $ans_1, ans_2, \dots, ans_n$.

Examples

Input 1

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

Output 1

3 4 6 8 5

Note

The following table shows the maximum $val_v$ in the expression for fixed $u$ and $i$:

Examples 2

See tree/tree2.in and tree/tree2.ans in the provided files. This example satisfies the constraints for test cases $3 \sim 5$.

Examples 3

See tree/tree3.in and tree/tree3.ans in the provided files. This example satisfies the constraints for test cases $9 \sim 10$.

Examples 4

See tree/tree4.in and tree/tree4.ans in the provided files. This example satisfies the constraints for test cases $11 \sim 12$.

Constraints

For all test cases, it is guaranteed that $1 \le T \le 5$, $1 \le n \le 5 \times 10^5$, $1 \le val_i \le 10^9$, $1 \le fa_i < i$, $c_i \in \{0, 1\}$, and $0 \le a_i \le n$.

The details are as follows:

Special Property A: $c_i = 0$. Special Property B: $fa_i = \lfloor \frac{i}{2} \rfloor$.