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

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

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

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

输入格式

从标准输入读入数据。

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

第二行一个正整数 。

第三行 个正整数，第 个数 表示 的父亲。

第四行 个正整数，第 个数为 。

输出格式

输出到标准输出。

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

样例一

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 \leq 2 \times 10^5$
• $1 \leq p_i < i$
• $1 \leq w_i \leq 10^9$

时间限制：

空间限制：

下载

样例数据下载