Bobo 拥有一棵有 $n$ 个节点的有根树，节点编号为 $1, 2, \dots, n$。节点 $1$ 是根节点，第 $i$ 个节点的权值为 $w_i$。

他想要计算 $f(2), f(3), \dots, f(n)$，其中 $$f(i) = \sum_{j=1}^{i-1} w_{\text{LCA}(i,j)}$$

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。

第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^4$)。

第三行包含 $(n-1)$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示从节点 $p_i$ 到节点 $i$ 的一条边 ($1 \le p_i \le n$)。这些边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $(n-1)$ 个整数：$f(2), f(3), \dots, f(n)$。

样例

样例输入 1

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

样例输出 1

1
2
1
3
5
4