求助万能的谷民，玄关

dXqwq 是个富可敌国的女孩子

她的公司有 n 位员工，编号为 1 ∼ n，她既是老板也是编号为 1 的员工，她的上司用 0 表示；而剩余的 员工都有一个比其编号更小的直接上司 pi。

保证对于每位员工，其恰好有偶数个直接下属。

现在公司在表决一起提案，第 i 位员工的意见是 ai，其中 0 代表不支持，1 代表支持

提案的审核方式是，对于 1 号员工，先询问其所有直接下属是否支持提案，如果支持者较多或不支持者

较多就采纳多数人的反馈，否则使用自己的意见作为反馈；而所有下属的反馈同样按照此规则计算。

不难发现，此时一些员工的意见没有任何意义，一个员工的意见有意义当且仅当如果他的意见改变，他 的反馈也会改变。

好在 dXqwq 可以贿赂一些员工：她可以花费 bi 的代价使第 i 位员工的意见改变。

dXqwq 想要对 x = 1 ∼ n 求出，如果要让第 x 位员工的意见有意义，她至少要花费的代价。

第一行输入一个整数 n。 接下来 n 行，每行输入三个整数 pi , ai , bi。

输出 n 行，每行包含一个整数，第 i 行输出使 i 的意见有意义的最小代价

本题共 10 个测试点，全部测试点满足 3 ≤ n ≤ 1 0 5 10 5 ，min(i − 1, 0) ≤ pi < i，0 ≤ ai ≤ 1，0 ≤ bi ≤ 1 0 9 10 9

样例输入

5 0 0 3 1 1 6 1 0 5 3 1 7 3 1 9 输出

6 0 7 0 0 对于样例，我们如果什么都不做，表决过程如下：

• 5 号员工的反馈为同意。

• 4 号员工的反馈为同意。

• 3 号员工的两个直接下属都反馈同意，所以反馈同意。

• 2 号员工的反馈为同意。

• 1 号员工的两个直接下属都反馈同意，所以反馈同意。

对于 x = 3 的情况，我们贿赂 4 号员工，使其意见变为不同意。

• 5 号员工的反馈为同意。

• 4 号员工的反馈为不同意。

• 3 号员工的两个直接下属意见不同，所以反馈自身意见不同意。

• 2 号员工的反馈为同意。

• 1 号员工的两个直接下属意见不同，所以反馈自身意见不同意。

此时不难发现如果 3 号员工的意见改变，其反馈的结果也会改变