Bobo 最近学习了动态规划，用于解决“最优二叉搜索树”问题。对于一个数字序列 $\{a_1, a_2, \dots, a_n\}$，$\text{OPT}(\{a_1, a_2, \dots, a_n\})$ 定义如下：

• 当 $n = 1$ 时，$\text{OPT}(\{a_1\}) = a_1$；
• 当 $n > 1$ 时，$\text{OPT}(\{a_1, a_2, \dots, a_n\}) = \min_{1 \le j < n} \text{OPT}(\{a_1, a_2, \dots, a_j\}) + \text{OPT}(\{a_{j+1}, a_{j+2}, \dots, a_n\}) + S$，其中 $S = a_1 + a_2 + \dots + a_n$。

Bobo 还有一棵树 $T$，其顶点编号为 $1, 2, \dots, n$。第 $i$ 个顶点关联的数字为 $a_i$。令 $P_i$ 为从顶点 $1$ 到顶点 $i$ 的路径上的数字序列。他想要计算出对于所有 $i = 1, 2, \dots, n$ 的 $\text{OPT}(P_i)$。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 4000$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。 第三行包含 $(n - 1)$ 个整数 $p_2, p_3, \dots, p_n$，其中 $p_i$ 表示顶点 $p_i$ 和 $i$ 之间的一条边 ($1 \le p_i < i$)。

输出格式

输出 $n$ 个整数，表示 $\text{OPT}(P_1), \text{OPT}(P_2), \dots, \text{OPT}(P_n)$。

样例

样例输入 1

3
1 2 3
1 2

样例输出 1

1
6
15

样例输入 2

3
1 2 3
1 1

样例输出 2

1
6
8