You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

大法师（dfs）

魔女宁宁作为一个法师，拥有一颗樱花树的掌控权。

这颗樱花树大小为 $n$，用 $n-1$ 条边连接。初始时，所有点的权值是 $1$。

现在，宁宁从根节点 $1$ 开始，按照深度优先搜索（dfs）的顺序进行游览这棵树（编号小的优先），每次到了一个也叶子节点 $u$（$u\not =1$）就会把这个叶子到 $1$ 路径上所有点的权值乘上 $a_u$。

每次走出一个叶子的时候，请告诉宁宁当前所有节点权值之和。

显然，非叶结点的 $a_u$ 是没用的，但是方便你进行输入还是给了你。

输入格式

从 $dfs.in$ 当中读入数据。

第一行一个正整数表示 $n$。

接下来 $n$ 个正整数表示 $a_i$。

接下来 $n-1$ 个数，表示点 $i+1$ 的父亲。

输出格式

输出答案到 $dfs.out$ 当中。

按照 dfs 的顺序对每个叶子输出答案。

测试样例

数据范围