Snuke 有一棵 $n$ 个点的有根树，每个点有权值 $w_i$，初始每个结点上都没有石子。

Snuke 准备了一些石子，并把它们拿在手中。她可以进行以下两种操作任意多次：

1. 从手中取 $w_i$ 个石子放在结点 $i$ 上，进行该操作要求结点 $i$ 的所有孩子 $j$ 上都有 $w_j$ 个石子。
2. 将结点 $i$ 上的所有石子收回手中。

Takahashi 想知道对于每个 $i$，为了在结点 $i$ 上放 $w_i$ 个石子，Snuke 至少需要准备多少石子。

输入格式

从标准输入读入数据。

第一行一个数字 $T$ 表示这个子任务的编号。

第二行一个正整数 $n$ 。$(n\le 2\times {10}^5)$

第三行 $n-1$ 个正整数，第 $i-1$ 个数 $p_i$ 表示 $i$ 的父亲。$(p_i<i)$

第四行 $n$ 个正整数，第 $i$ 个数为 $w_i$ 。

输出格式

输出到标准输出。

输出一行 $n$ 个正整数，第 $i$ 个数为结点 $i$ 的答案。

样例一

input

0
3
1 2
1 1 1

output

2 2 1

样例二

input

0
3
1 1
1 1 1

output

3 1 1

限制及约定

对于所有数据，保证：

• $n\le 2\times {10}^5$
• $1\le p_i<i$
• $1\le w_i\le {10}^9$

时间限制：$3\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载