小V 是个富可敌国的女孩子。
她的公司有 n 位员工，编号为 1∼n，她既是老板也是编号为 1 的员工，她的上司用 0 表示；而剩余的员工都有一个比其编号更小的直接上司 pi。
保证对于每位员工，其恰好有偶数个直接下属。
现在公司在表决一起提案，第 i 位员工的意见是 ai，其中 0 代表不支持，1 代表支持。
提案的审核方式是，对于 1 号员工，先询问其所有直接下属是否支持提案，如果支持者较多或不支持者较多就采纳多数人的反馈，否则使用自己的意见作为反馈；而所有下属的反馈同样按照此规则计算。
不难发现，此时一些员工的意见没有任何意义，一个员工的意见有意义当且仅当如果他的意见改变，他的反馈也会改变。
好在 小V 可以贿赂一些员工：她可以花费 bi 的代价使第 i 位员工的意见改变。
小V 想要对 x=1∼n 求出，如果要让第 x 位员工的意见有意义，她至少要花费的代价。

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

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

样例二：
输入：


输出：


样例三：
输入：


输出：

样例解释

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

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

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

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

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

第三题