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:
For all 1 \leq i < n, -th distributor will give all his money to its direct supervisor (all of them do this simultaneously).
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.
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.
For each test case print integers — the amount of money Walter would collect after shouting exactly times, for all from to n-1.
Example
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.