有一个包含 $n$ 个顶点的有根树，根节点为 $1$。每个顶点上都有一只怪物。第 $i$ 个顶点上怪物的生命值为 $hp_i$。
Kotori 想要杀死所有的怪物。只有当第 $i$ 个顶点的直接父节点上的怪物已经被杀死时，第 $i$ 个顶点上的怪物才能被杀死。杀死第 $i$ 个怪物所需的能量为 $hp_i$ 加上所有存活的、且直接父节点为 $i$ 的顶点 $j$ 上的怪物的生命值之和。形式化地，能量等于：
$$hp_i + \sum_{\substack{\text{顶点 } j \text{ 上的怪物存活} \\ \text{且 } i \text{ 是 } j \text{ 的直接父节点}}} hp_j$$
此外，Kotori 可以使用一些魔法。如果她使用一个魔法，她可以不消耗任何能量杀死任意一只怪物，且没有任何限制。也就是说，即使该怪物的直接父节点上的怪物尚未被杀死，她也可以选择这只怪物。
对于每个 $m = 0, 1, 2, \dots, n$，Kotori 想知道如果她可以使用 $m$ 个魔法，杀死所有怪物所需的最小总能量。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：
第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^3$)，表示顶点的数量。
第二行包含 $(n - 1)$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)，其中 $p_i$ 表示顶点 $i$ 的直接父节点。
第三行包含 $n$ 个整数 $hp_1, hp_2, \dots, hp_n$ ($1 \le hp_i \le 10^9$)，表示每只怪物的生命值。
保证所有测试数据的 $n$ 之和不超过 $2 \times 10^3$。
输出格式
对于每组测试数据，输出一行包含 $(n + 1)$ 个整数 $a_0, a_1, \dots, a_n$，用空格分隔，其中 $a_m$ 表示如果 Kotori 可以使用 $m$ 个魔法，杀死所有怪物所需的最小总能量。
请不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！
样例
样例输入 1
3 5 1 2 3 4 1 2 3 4 5 9 1 2 3 4 3 4 6 6 8 4 9 4 4 5 2 4 1 12 1 2 2 4 5 3 4 3 8 10 11 9 1 3 5 10 10 7 3 7 9 4 9
样例输出 1
29 16 9 4 1 0 74 47 35 25 15 11 7 3 1 0 145 115 93 73 55 42 32 22 14 8 4 1 0