Breaking Bad#12922

Breaking Bad

Walter White finally broke bad and finished building his drug empire.

He has a network of distributors, which looks like a tree. Jesse is the head distributor, numbered . For every i\geq 1, -th distributor has a direct supervisor  — distributor p_i with p_i < i. Initially, distributor has a_i dollars.

Walter is going to shout for times. Every time Walter shouts, the following will happen:

After shouting times, Walter will choose the distributor with the maximum amount of money and collect all his money.

For all from to n-1, find the amount of money Walter would collect after shouting exactly times.

Input

The first line of input contains a single integer (1 \leq t \leq 2 \cdot 10^5) — the number of test cases. The description of test cases follows.

The first line of each test case consists of a single integer (1 \le n \le 2 \cdot 10^5)  — the number of distributors.

The second line of each test case consists of n-1 integers p_1,p_2,\dots,p_{n-1} (0 \le p_i < i)  — where p_i is a direct supervisor of distributor .

The third line of each test case consists of integers a_0,a_1,\dots,a_{n-1} (0 \le a_i \le 10^9) — the initial amounts of money that distributors have.

It is guaranteed that sum of over all test cases does not exceed 2 \cdot 10^5.

Output

For each test case print integers  — the amount of money Walter would collect after shouting exactly times, for all from to n-1.

Examples

Example

Loading
Loading

Note

Consider the first test case.

  • If Walt shouts times, the amounts of money of distributors are (1, 3, 4, 2). So, he will collect dollars.

  • If Walt shouts time, the amounts of money of distributors are (4, 6, 0, 0). So, he will collect dollars.

  • If Walt shouts times, the amounts of money of distributors are (10, 0, 0, 0). So, he will collect dollars.

  • If Walt shouts times, the amounts of money of distributors are (10, 0, 0, 0). So, he will collect dollars.